39. Combination Sum

CombinationSum.java

class Solution {
    
    // 39. Combination Sum
    // https://leetcode.com/problems/combination-sum/

    public List<List<Integer>> combinationSum(int[] nums, int target) {
        List<List<Integer>> list = new ArrayList<>();
        Arrays.sort(nums);
        backtrack(list, new ArrayList<>(), nums, target, 0);
        return list;
    }

    private void backtrack(List<List<Integer>> list, List<Integer> tempList, int [] nums, int remain, int start){
        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 ((remain - nums[i]) < 0) break;
                tempList.add(nums[i]);
                backtrack(list, tempList, nums, remain - nums[i], i); // not i + 1 because we can reuse same elements
                tempList.remove(tempList.size() - 1);
            }
        }
    }
}