Questions tagged [subset-sum-problem]

Given a set or multiset of integers, is there a non-empty subset whose sum is zero? The subset sum problem can be extended to find the sum to any given integer. The subset sum problem is a special case of the knapsack problem.

Filter by
Sorted by
Tagged with
3 votes
1 answer
101 views

A Subset-Sum Solver Using Roots of Unity

This program solves a version of the subset-sum problem: given a set of non-negative integers \$S=\{a_1,a_2,\cdots,a_n\}\$ (they may not be distinct) and a non-negative integer \$s\$, decide whether ...
Soha's user avatar
  • 31
7 votes
3 answers
370 views

Leetcode Three Sum

From here: Given an array nums of n integers, are there elements a, b, c in nums such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero. Note: The ...
enderland's user avatar
  • 1,726
4 votes
1 answer
157 views

Subset Sum in Ada

One of my favorite classic programming exercises is the Subset Sum problem. I'm (trying) to learn Ada and it's the first thing I wanted to implement, even before a Hello World. The Subset Sum ...
gator's user avatar
  • 455
2 votes
2 answers
216 views

Python set based solution to Subset Sum

Working on the 2 element subset sum problem (finding two numbers in a list that sum to a given value), I came up with a relatively short solution code-wise. The code could fit on a single line but I'...
Cooper's user avatar
  • 21
4 votes
2 answers
6k views

Finding all the subsets in an array of integers that sum to a given target

Problem Statement: Given an Array if ints, Find out all the subsets in the Array that sum to a given target value. Example: If the input array is: ...
Anirudh's user avatar
  • 872