Combination Sum 2

Problem Statement:

Given a collection of candidate numbers (candidates) and a target number (target), find all unique combinations in candidates where the candidate numbers sum to target. Each number in candidates may only be used once in the combination. Note: The solution set must not contain duplicate combinations.

Example 1:

Input: candidates = [10,1,2,7,6,1,5], target = 8 Output: [ [1,1,6], [1,2,5], [1,7], [2,6] ]

Example 2:

Input: candidates = [2,5,2,1,2], target = 5 Output: [ [1,2,2], [5] ]

Constraints:

• 1 <= candidates.length <= 100
• 1 <= candidates[i] <= 50
• 1 <= target <= 30

Solution:

class Solution {
    public void combinationSumUtil(int idx, int[] nums, int target, List<Integer> temp, List<List<Integer>> res){
        if (target == 0) {
            res.add(new ArrayList<>(temp));
            return;
        }
        if (target < 0 || idx == nums.length) {
            return;
        }
 
        //Pick
        temp.add(nums[idx]);
        combinationSumUtil(idx + 1, nums, target - nums[idx], temp, res);
        temp.remove(temp.size() - 1);
 
        //Not Pick
        //1st skip duplicates before not picking to avoid reaching to an option which was already picked earlier,
        //if picked then it should never be picked again.
        while(idx + 1 < nums.length && nums[idx] == nums[idx + 1]) idx++; 
        
        combinationSumUtil(idx + 1, nums, target, temp, res);
    }
    public List<List<Integer>> combinationSum2(int[] nums, int target) {
        List<List<Integer>> res = new ArrayList<>();
        Arrays.sort(nums);
        combinationSumUtil(0, nums, target, new ArrayList<>(), res);
 
        return res;
    }
}