Skip to content

Instantly share code, notes, and snippets.

@anil477
Created January 29, 2022 13:58
Show Gist options
  • Save anil477/db40a1126d9ba9abdf140a5327cf9d23 to your computer and use it in GitHub Desktop.
Save anil477/db40a1126d9ba9abdf140a5327cf9d23 to your computer and use it in GitHub Desktop.
39. Combination Sum
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);
}
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment