Can anyone figure out the error in this DFS solution to a problem

Question

Problem : Given a collection of candidate numbers (candidates) and a target number (target), find all unique combinations in candidates where the candidate numbers sum to target. Each number in candidates may only be used once in the combination. Note: The solution set must not contain duplicate combinations.

Example 1:

Input: candidates = [10,1,2,7,6,1,5], target = 8
Output: 
[
[1,1,6],
[1,2,5],
[1,7],
[2,6]
]

Example 2:

Input: candidates = [2,5,2,1,2], target = 5
Output: 
[
[1,2,2],
[5]
]
 
Constraints:

1 <= candidates.length <= 100
1 <= candidates[i] <= 50
1 <= target <= 30

My Solution : Since this is a backtracking problem, I went ahead with a dfs approach where i check each subsequence along with its sum and accordingly generate the result. For handling the duplicate solutions issue, I sort the temp array before adding it into the resulting set result in the form of a tuple.

But here's the thing; my approach if working fine for the 1st example but there's a weird issue I'm facing with the 2nd example.

class Solution:
    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
        def dfs(ind, temp, sum):
            if ind >= n:
                if sum == target:
                    temp.sort()
                    result.add(tuple(temp))
                return
            if sum < target:
                temp.append(candidates[ind])
                sum += candidates[ind]
                dfs(ind + 1, temp, sum)
                temp.pop()
                sum -= candidates[ind]
            dfs(ind + 1, temp, sum)
        temp, n = [], len(candidates)
        result = set()
        dfs(0, temp, 0)
        return result

The 1st example runs well, but here's the output I'm getting for the 2nd example:

candidates =
[2,5,2,1,2]
target =
5

Output
[[1,2,2],[5],[1,1,2]]
Expected
[[1,2,2],[5]]

There is this weird tuple (1,1,2) getting added to the resultant set when there's only one 1 present in the input array. I tried debugging but so far no clue.

Can someone help me figure out where I'm going wrong?

............................

Answer 1

Here is an answer inspired by your original code using backtracking.

def combinationSum2(candidates, target):
   result = set()

   def dfs(ind, temp, sum):
      if sum == 0:
         result.add(tuple(sorted(temp)))
         return
      if sum < 0:
         return
      
      for i in range( ind, len(candidates)):
         dfs(i+1,temp + [candidates[i]],sum - candidates[i])

   dfs(0, [], target)
   return result

l = [2,5,2,1,2]

print( combinationSum2(l,5))

Answer 2

The immediate cause of the problem you encountered is temp.sort(). This affects a list that is shared by all execution contexts of dfs, and so when later a caller performs temp.pop(), this may not pop the intended element from temp, as now temp is sorted.

To fix this you can return tuple(sorted(temp)).

But your algorithm is not efficient enough. For instance for this this input:

[1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1]
30

...your algorithm will lose itself in producing all possible combinations of making 30 selections out of this list of 100 entries. That's more than 10²⁵ possibilities!

Improved algorithm

To overcome checking useless combinations, first determine how many you have of each distinct value in the input. Then vary how many you will take (per recursion level) from a given (distinct) value.

Some other comments on your code:

• Don't name a variable sum. This name is already taken for a native sum function
• Don't name a variable temp. Use a name that describes what it contains. As it is a list that has selections from your input list, you could call it selections.

Here is an implementation of the described algorithm:

class Solution:
    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
        counter = list(Counter(candidates).items())
        results = []

        def dfs(index, selections, total):  # Don't use sum nor temp as name
            if total == target:
                results.append(selections)
                return
            if index >= len(counter):
                return
            value, frequency = counter[index]
            for take, consumed in zip(range(frequency + 1), range(total, target + 1, value)):
                dfs(index + 1, selections + [value] * take, consumed)

        dfs(0, [], 0)
        return results