I want get possible subsets, for example: input is {1, 2, 3}
expected result:
1
2
3
1,2
1,3
1,2,3
2,3
i use recursion to implement it, it think it is very slow, does it have more effective way?
1
-
Is it a programming contest ? Can you provide a link to the question ?fjardon– fjardon2015-11-13 12:24:47 +00:00Commented Nov 13, 2015 at 12:24
Add a comment
|
3 Answers
This is a variant of subset sum problem, that can be solved in O(n*SUM), where SUM is the sum of all number, using Dynamic Programming.
D(i,x) = D(i-1,x) OR D(i-1,x-arr[i])
D(0,0) = true
D(0,x) = false x != 0
In here, D(i,x) gives a boolean value that indicates if sum x can be reached using some or all of the i first elements. Thus, for each possible sum x, D(n,x) indicates if this sum can be reached using any number.
6 Comments
Tony
i read the dynamic programming, still don't know how to write code. could you help me? we can chat on some im tool
Tony
but your comment is very helpful, now, i know i need find all subsets, then get them sum
Tony
i want use dynamic programming to find the answer, i hope you can give me some help which is how do i think about this question
amit
@CarlXu Did you read the links I provided about Dynamic Programming and about Subset Sum Problem? Do you understand how to implement D(i,x) as recursive function in your favorite programming language?
Tony
that is so complex for me, can you provide some simple understand doc about DP
|
You could think about a recursive approach:
- if you have only one number it is the only possible sum
- if you have more than one number, than for each number: take the number it combined with all possible sums of the remaining numbers are also sums.
PSEUDO CODE:
allsums = makeAllSums(setOfNumbers){
if(1==setOfNumbers.size)
return setOfNumbers.head
result = emptySet
for(a in setOfNumbers)
allSubSums=makeAllSums(setOfNumbers without a);
for(b in allSubSums)
result.add(a."+".b)
return result
}
Than you have only to think about avoiding duplicates.
Idea based on a binary number representation of the elements to add to a sum
from the initial set.
1 2 3 4 5 6 7 9 10
Every possible sum can be written as a 8 digit binary number where each digit stands for 'take this in the sum' of 'do not take this in the sum'.
Example:
001010100 means 3+5+7
111111111 means 1+2+3+4+5+6+7+9+10
000000001 means 10
010000000 means 2
So every possible sum can be written as a sequence of 0 and 1 of length 9.
All sums are all possible sequences of length 9.
So you can simply make a loop of the numbers 1 to 2^9-1 and interpret the binary representation as a sum.
000000001 : 10
000000010 : 9
000000011 : 9 + 10
000000100 : 7
000000101 : 7 + 10
...
111111111 : 1+2+3+4+5+6+7+9+10
This way you get all sums (no duplicates)