Combination Sum

Question

Given a set of candidate numbers (C) (without duplicates) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.

The same repeated number may be chosen from C unlimited 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 target 7, A solution set is:

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

Tags

• Array
• Backtracking

Thought

We still used the backtracking algorithm to solve the problem.

The start of the problem is target = target and the end of the problem is target = 0. The recursion is used to check each paths and skip the incorrect path.

Code

class Solution(object):
    def combinationSum(self, candidates, target):
        """
        :type candidates: List[int]
        :type target: int
        :rtype: List[List[int]]
        """
        def helper(number, res, result, solution):
            for i in xrange(len(number)):
                if i != len(number) - 1 and number[i] == number[i + 1]:
                    continue
                num = number[i]
                if res - num == 0:
                    result.append(solution + [num])
                elif res - num < 0:
                    continue
                else:
                    helper(number[i:], res - num, result, solution + [num])
            return result

        return helper(sorted(candidates), target, [], [])