Java: Combination Sum

Thought Process

To solve the Combination Sum problem, we use backtracking. We start by iterating through the candidates array and recursively build combinations that sum up to the target. If the sum exceeds the target, we backtrack and try the next candidate. 

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++){

            // Add an Element to the List and Taking that element try to find the solution
            tmp.add(candidates[i]);
            backTrack(ans,tmp,candidates,target-candidates[i],i);
            // Finally, remove the added Element (backTrackStep)
            tmp.remove(tmp.size()-1);
        }

    }
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        
        List<List<Integer>> ans = new ArrayList<>();
        List<Integer> tmp = new ArrayList<>();

        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, 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!