pylist

153. Combination Sum II

Given an array num and a number target. Find all unique combinations in num where the numbers sum to target.

Each number in num can only be used once in one combination. All numbers (including target) will be positive integers. Numbers in a combination a1, a2, … , ak must be in non-descending order. (ie, a1 ≤ a2 ≤ … ≤ ak) Different combinations can be in any order. The solution set must not contain duplicate combinations.

Example 1:

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

Example 2:

Input: num = [1,1,1], target = 2
Output: [[1,1]]
Explanation: The solution set must not contain duplicate combinations.

solution

class Solution:
    """
    @param candidates: A list of integers
    @param target: An integer
    @return: A list of lists of integers
    """
    def combinationSum2(self, candidates, target):
        ans = []
        cur = []
        csum = 0
        self.traverse(sorted(candidates), target, ans, cur, csum)
        return ans
    
    def traverse(self, candidates, target, ans, cur, csum):
        if csum == target:
            ans.append(cur[:])
            return
        if csum > target:
            return
        
        for i, c in enumerate(candidates):
            if i > 0:
                if c == candidates[i-1]:
                    continue
            cur.append(c)
            csum += c
            self.traverse(candidates[i+1:], target, ans, cur, csum)
            csum -= c
            cur.pop()
        return 

135. Combination Sum

Given a set of candidtate numbers candidates and a target number target. Find all unique combinations in candidates where the numbers sums to target.

The same repeated number may be chosen from candidates unlimited number of times.

All numbers (including target) will be positive integers. Numbers in a combination a1, a2, … , ak must be in non-descending order. (ie, a1 ≤ a2 ≤ … ≤ ak) Different combinations can be in any order. The solution set must not contain duplicate combinations.

Example 1

Input: candidates = [2, 3, 6, 7], target = 7
Output: [[7], [2, 2, 3]]

Example 2:

Input: candidates = [1], target = 3
Output: [[1, 1, 1]]

Solution

只有一行的差别。

self.traverse(candidates[i:], target, ans, cur, csum)

care