Simple JAVA solution based on Combination Sum


  • 0
    T
    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(-1);
        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 + 1; i < candidates.length; i++) {
                    if (i > begin + 1 && candidates[i] == candidates[i - 1])
                        continue;
                    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.