CODEWITHSUNDEEP
javaalgorithm
Tony
Tony

Reputation: 117

input is int array, get all subsets

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?

Upvotes: 1

Views: 76

Answers (3)

MrSmith42
MrSmith42

Reputation: 10151

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)

Upvotes: 0

MrSmith42
MrSmith42

Reputation: 10151

You could think about a recursive approach:

  1. if you have only one number it is the only possible sum
  2. 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.

Upvotes: 1

amit
amit

Reputation: 178411

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.

Upvotes: 1

Related Questions