Combination Sum

此题可以理解为列出背包问题的所有装满方案，核心代码就在于排序和对递归调用的helper函数设定起始点为i这两处，第一处保证所有值都是有序排列帮助我们减枝，第二处保证了不会回头取重复点即不会同时出现2，2，3和2，3，2这种情况，下面是代码

class Solution(object):
    def combinationSum(self, candidates, target):
        """
        :type candidates: List[int]
        :type target: int
        :rtype: List[List[int]]
        """
        tmp, res = [], []
        candidates.sort()
        self.helper(candidates, target, tmp, res, 0, len(candidates))
        return res

    def helper(self, candidates, target, tmp, res, start, end):
        if target == 0:
            ref = tmp[:]
            res.append(ref)
            return 

        for i in xrange(start, end):
            if target < candidates[i]:
                break
            tmp.append(candidates[i])
            self.helper(candidates, target - candidates[i], tmp, res, i, end)
            tmp.pop()

Java版本

class Solution {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        Arrays.sort(candidates);
        List<List<Integer>> result = new ArrayList<>();
        List<Integer> tmp = new ArrayList<>();
        helper(candidates, 0, 0, target, tmp, result);
        return result;
    }

    private void helper(int[] nums, int start, int base, int target, List<Integer> tmp, List<List<Integer>> result) {
        if (base >= target) {
            if (base == target) {
                result.add(new ArrayList<Integer>(tmp));
            }
            return;
        }

        if (start == nums.length) {
            return;
        }

        for (int i = start; i < nums.length; i++) {
            if (nums[i] + base <= target) {
                tmp.add(nums[i]);
                helper(nums, i, base + nums[i], target, tmp, result);
                tmp.remove(tmp.size() - 1);
            } else {
                break;
            }
        }
    }
}

Combination Sum II

此题和上题的不同是candidates可以有重复数但每个数只能用一次，对于这个条件我们只需要将递归调用的函数参数从i改成i + 1就可以了，另外我们需要加入一个对集合查重的if语句，下面是代码

class Solution(object):
    def combinationSum2(self, candidates, target):
        """
        :type candidates: List[int]
        :type target: int
        :rtype: List[List[int]]
        """
        tmp, res = [], []
        candidates.sort()
        self.helper(candidates, target, tmp, res, 0, len(candidates))
        return res

    def helper(self, candidates, target, tmp, res, start, end):
        if target == 0:
            ref = tmp[:]
            res.append(ref)
            return 

        for i in xrange(start, end):
            if target < candidates[i]:
                break
            if i > start and candidates[i] == candidates[i - 1]:
                continue
            tmp.append(candidates[i])
            self.helper(candidates, target - candidates[i], tmp, res, i + 1, end)
            tmp.pop()

Java版本

class Solution {
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        Arrays.sort(candidates);
        List<Integer> tmp = new ArrayList<>();
        List<List<Integer>> result = new ArrayList<>();
        helper(candidates, 0, target, tmp, result);
        return result;
    }

    private void helper(int[] nums, int start, int target, List<Integer> tmp, List<List<Integer>> result) {
        if (target == 0) {
            result.add(new ArrayList<>(tmp));
            return;
        }

        Set<Integer> checker = new HashSet<>();
        for (int i = start; i < nums.length; i++) {
            if (target - nums[i] >= 0) {
                if (!checker.contains(nums[i])) {
                    checker.add(nums[i]);
                    tmp.add(nums[i]);
                    helper(nums, i + 1, target - nums[i], tmp, result);
                    tmp.remove(tmp.size() - 1);
                }
            } else {
                break;
            }
        }
    }
}

Combination Sum III

普通回溯题而已，计数，查重一起就搞定

class Solution(object):
    def combinationSum3(self, k, n):
        """
        :type k: int
        :type n: int
        :rtype: List[List[int]]
        """
        tmp, res = [], []
        self.helper(1, 10, tmp, res, k, n, 0)
        return res

    def helper(self, start, end, tmp, res, limit, target, count):
        if count == limit:
            if target == 0:
                res.append(tmp[:])
            return 

        for i in xrange(start, end):
            if target >= i:
                tmp.append(i)
                self.helper(i + 1, end, tmp, res, limit, target - i, count + 1)
                tmp.pop()
            else:
                break