40. Combination Sum II

CombinationSumII.java

class Solution {
    
    
    // https://leetcode.com/problems/combination-sum-ii/
    // 40. Combination Sum II

    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        List<List<Integer>> list = new ArrayList<>();
        Arrays.sort(candidates);
        boolean[] used = new boolean[candidates.length];
        backtrack(list, new ArrayList<>(), candidates, target, 0, used);
        return list;
    }
    
    
    
     private void backtrack(List<List<Integer>> list, List<Integer> tempList, int [] nums, int remain, int start, boolean[] used){
        if(remain < 0) return;
        else if(remain == 0) list.add(new ArrayList<>(tempList));
        else{ 
            // if we set = 0, then we will have same combinations showing up multiple times. 
            // for i/p = [2,3,6,7] and target = 7, o/p will be -> [[2,2,3],[2,3,2],[3,2,2],[7]]
            // so if we don't start from the base case, then we will end up with the same permutation again
            for(int i = start; i < nums.length; i++){
                if (used[i]) continue;
                if (i>0 && nums[i] == nums[i-1] && !used[i-1]) continue;
                used[i] = true;
                // //. do not break as their are duplicates 
                // if ((remain - nums[i]) < 0) break;
                tempList.add(nums[i]);
                backtrack(list, tempList, nums, remain - nums[i], i, used); // not i + 1 because we can reuse same elements
                used[i] = false;
                tempList.remove(tempList.size() - 1);
            }
        }
    }
}