moonlightshadow123
6/23/2017 - 4:23 PM

39. Combination Sum

  1. Combination Sum
solution.py
content_copyfile_download
class Solution(object):
    def combinationSum(self, candidates, target):
        """
        :type candidates: List[int]
        :type target: int
        :rtype: List[List[int]]
        """
        self.res = []
        self.cur = []
        self.backtracking(candidates,0, target)
        return self.res
    def backtracking(self, nums, startIdx, target):
        # Combine elements from startIdx (including) to the end, to sum up to target.
        if target < 0:
            return
        if target == 0:
            self.res.append([each for each in self.cur])
            return
        for curIdx in range(startIdx,len(nums)):
            curNum = nums[curIdx]
            self.cur.append(curNum)
            self.backtracking(nums, curIdx, target-curNum)
            # If same element can occur multiple times, backtracking(,curIdx,)
            # if same element can't occur multiple times, backtracking(,curIdx+1,)
            del self.cur[-1]
39-Combination-Sum.md
content_copyfile_download
  • Rendered
  • Source

https://leetcode.com/problems/combination-sum/#/description

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]
]