I kind of get it but can someone explain how does this work to prevent duplicates?
If i is the same as order, then nums[i] is being included for the first time as a candidate.
But if i > order, then nums[i] is starting over using a duplicate number. Is this correct?
def combinationSum2(self, candidates, target):
dp = [set() for i in xrange(target+1)]
for num in candidates:
for t in xrange(target, num-1, -1):
for prev in dp[t-num]:
dp[t].add(prev + (num,))
For the uninitiated, basically, this problem is a variant of the knapsack problem. If you can understand the solution to Coin Change or Coin Change 2, then you can easily understand this solution. One caveat here is that the inner loop is reversed for t in xrange(target, num-1, -1), because each number can only be used once.
Food for thought - what happens if we don't reverse the inner loop? Can that be used to solve Combination Sum?
@tju_xu97@IvesWang Very cool! I had a similar question, is it possible to get combination closest? As in if there's a solution set whos sum is closest to the target val.. (I know there's a 3 sum closest, but I couldn't figure it out with combination sum closest)
@teddyyyy Good observation but I think that's not a problem. Given the input [1, 1] and the target is 2. The [1,1] will return simplly handled by the if statement i == start condition in another level of recursion