Combination Sum

Given asetof candidate numbers (C)(without duplicates)and a target number (T), find all unique combinations inCwhere the candidate numbers sums toT.

Thesamerepeated number may be chosen fromCunlimited number of times.

Note:

• All numbers (including target) will be positive integers.
• The solution set must not contain duplicate combinations.

For example, given candidate set[2, 3, 6, 7]and target7,
A solution set is:

[
  [7],
  [2, 2, 3]
]

Solution

Time complexity: exponential. O( 2^n)

Basic idea: sort, dfsVisit and for loop in the dfsVisit.

Tricky part: what do you iterate on.

1. Shouldn't be from 0 every time, because if it's sorted already, then going back to previous number is just doing the repetitive work and is permutation instead.
   1. for looping from 0 to len(n) is permutation for sure

2. Thus for our case, we loop from specified position.

   1. but, because the problem allow using the same unique number repetitively. We don't need to increment pos by 1 when going into sub recursion call of dfsVisits. Namely this line:

   2. elif num < target:
          self.dfsVisit(nums, i, cur + [num], res, target - num)
      

class Solution(object):
    def combinationSum(self, candidates, target):
        """
        :type candidates: List[int]
        :type target: int
        :rtype: List[List[int]]
        """

        nums = sorted(candidates)
        res = []
        self.dfsVisit(nums, 0, [], res, target)
        return res

    def dfsVisit(self, nums, pos, cur, res, target):

        for i in range(pos, len(nums)):
            num = nums[i]
            if num == target:
                res.append(cur[:] + [num])
                return
            elif num < target:
                self.dfsVisit(nums, i, cur + [num], res, target - num)
            else:
                return