Skip to content

Instantly share code, notes, and snippets.

@anil477
Created January 29, 2022 14:05
Show Gist options
  • Save anil477/1e8005618dc2b7d338f67b236eef658c to your computer and use it in GitHub Desktop.
Save anil477/1e8005618dc2b7d338f67b236eef658c to your computer and use it in GitHub Desktop.
40. Combination Sum II
class Solution {
// https://leetcode.com/problems/combination-sum-ii/
// 40. Combination Sum II
public List<List<Integer>> combinationSum2(int[] candidates, int target) {
List<List<Integer>> list = new ArrayList<>();
Arrays.sort(candidates);
boolean[] used = new boolean[candidates.length];
backtrack(list, new ArrayList<>(), candidates, target, 0, used);
return list;
}
private void backtrack(List<List<Integer>> list, List<Integer> tempList, int [] nums, int remain, int start, boolean[] used){
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 (used[i]) continue;
if (i>0 && nums[i] == nums[i-1] && !used[i-1]) continue;
used[i] = true;
// //. do not break as their are duplicates
// if ((remain - nums[i]) < 0) break;
tempList.add(nums[i]);
backtrack(list, tempList, nums, remain - nums[i], i, used); // not i + 1 because we can reuse same elements
used[i] = false;
tempList.remove(tempList.size() - 1);
}
}
}
}
@anil477
Copy link
Author

anil477 commented Jan 29, 2022

Screenshot 2022-01-29 at 8 53 38 PM

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment