Java: Combination Sum II

Thought Process

To solve the Combination Sum II problem, we use backtracking with duplicate handling. First, we sort the candidates array to group duplicates together. During the backtracking process, we skip duplicate elements to avoid redundant combinations. This ensures that we generate only unique combinations that sum up to the target. 

class Solution {

    void backTrack(List<List<Integer>> ans, List<Integer> tmp, int[] candidates, int target, int start){

        if(target==0)
            ans.add(new ArrayList<>(tmp));

        if(target<0)
            return;

        for(int i=start;i<candidates.length;i++){

            // To remove the duplicates, if current element is equal to previous elememt
            // then we will skip the iteration
            if(i>start && candidates[i]==candidates[i-1])
                continue;
            tmp.add(candidates[i]);
            backTrack(ans,tmp,candidates,target-candidates[i],i+1);
            tmp.remove(tmp.size()-1);
        }
    }
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {

        List<List<Integer>> ans = new ArrayList<>();
        List<Integer> tmp = new ArrayList<>();
        Arrays.sort(candidates);

        backTrack(ans,tmp,candidates,target,0);
        return ans;
    }
}

Code Complexity

Time Complexity: O(2n)

The algorithm explores all possible combinations of the candidates, leading to an exponential time complexity. Sorting adds an additional O(n log n), where 'n' is the size of the input.

Space Complexity: O(n)

The recursion stack depth is proportional to the size of the input('n'), and the temporary list stores intermediate results.

Code copied!