Java solution using backtracking, solve by loop, non-recursive


  • 0
    Z

    Using set to remove duplicate. using two stack for track both combination and index.

        public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        Set<List<Integer>> result = new LinkedHashSet<>();
        Arrays.sort(candidates);
    
        Stack<Integer> com = new Stack<>();
        Stack<Integer> indexs = new Stack<>();
        int sum = 0, index = 0;
        while (index < candidates.length) {
            if (sum + candidates[index] >= target) {
                if (sum + candidates[index] == target) {
                    com.push(candidates[index]);
                    result.add(new ArrayList<>(com));
                    com.pop();
                }
                if (!indexs.isEmpty()) {
                    sum -= com.pop();
                    index = indexs.pop();
                }
            } else {
                sum += candidates[index];
                com.push(candidates[index]);
                indexs.push(index);
            }
            while (index == candidates.length - 1 && !indexs.empty()) {
                index = indexs.pop();
                sum -= com.pop();
            }
            index++;
        }
        return new ArrayList<>(result);
    }

Log in to reply
 

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