Combination Sum

Problem: Combination Sum

It's a typical backtracking problem. We can stop backtracking earlier if current sum exceeds target.

Code in Python:

class Solution(object):
    def combinationSum(self, candidates, target):
        """
        :type candidates: List[int]
        :type target: int
        :rtype: List[List[int]]
        """
        ans, length, candidates = [], len(candidates), sorted(candidates)
        def combSum(pos, target, combination):
            for i in xrange(pos, length):
                if candidates[i] < target:
                    combSum(i, target-candidates[i], combination + [candidates[i]])
                elif candidates[i] == target:
                    ans.append(combination + [candidates[i]])
                else:
                    break
        combSum(0, target, [])
        return ans

Code in Java:

public class Solution {

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

    public void helper(int[] candidates, int location, List<Integer> combination, int sum, int target, List<List<Integer>> res) {
        if (sum == target) {
            res.add(new ArrayList<>(combination));
            return;
        }
        for (int i = location; i < candidates.length; i++) {
            if (sum + candidates[i] > target) break;
            combination.add(candidates[i]);
            helper(candidates, i, combination, sum+candidates[i], target, res);
            combination.remove(combination.size()-1);
        }
    }
}