Simple and fast DFS solution, python AC 98ms


  • 6
    T
    class Solution:
    # @param candidates, a list of integers
    # @param target, integer
    # @return a list of lists of integers
    def combinationSum(self, candidates, target):
        candidates.sort()
        stack = [(0, 0, [])]
        result = []
        while stack:
            total, start, res = stack.pop()
            if total == target:
                result.append(res)
            for n in range(start, len(candidates)):
                t = total + candidates[n]
                if t > target:
                    break
                stack.append((t, n, res + [candidates[n]]))
        return result
    

    JAVA

    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        Arrays.sort(candidates);
        Stack<ArrayList<Integer>> stack = new Stack<ArrayList<Integer>>();
        Stack<Integer> sum = new Stack<Integer>();
        Stack<Integer> start = new Stack<Integer>();
        stack.push(new ArrayList<Integer>());
        sum.push(0);
        start.push(0);
        List<List<Integer>> result = new ArrayList<List<Integer>>();
        while (!stack.isEmpty()) {
            List<Integer> res = stack.pop();
            int total = sum.pop();
            int begin = start.pop();
            if (total == target)
                result.add(res);
            else {
                for (int i = begin; i < candidates.length; i++) {
                    int t = total + candidates[i];
                    if (t > target)
                        break;
                    ArrayList<Integer> r = new ArrayList<Integer>(res);
                    r.add(candidates[i]);
                    stack.push(r);
                    sum.push(t);
                    start.push(i);
                }
            }
        }
        return result;
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.