class Solution {
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        // sorting the candidates to avoid duplicated during recursion
        Arrays.sort(candidates);
        List<List<Integer>> result = new ArrayList<>();
        List<Integer> temp = new ArrayList<>();

        findCombinationSumWithoutDuplicates(candidates, target, 0, result, temp);
        return result;
    }


    public void findCombinationSumWithoutDuplicates(int[] nums, int target, int index, List<List<Integer>> result, List<Integer> temp)
    {
        // Base condition 1: when target becomes 0
        if(target == 0)
        {
            result.add(new ArrayList<>(temp));
            return;
        }

        // Base condition 2: when we reach end of the array
        if(index == nums.length)
            return;
        

        // pick the element
        if(nums[index] <= target)
        {
            temp.add(nums[index]);
            // i+1 because each number used once
            findCombinationSumWithoutDuplicates(nums, target - nums[index], index+1, result, temp); 

            // do not pick the element
            temp.remove(temp.size() - 1);
        }

        // skip the duplicates
        while(index+1 < nums.length && nums[index] == nums[index+1])
            index++;
        
        findCombinationSumWithoutDuplicates(nums, target, index+1, result, temp);
        return;
    }
}