combination sum ii | combination sum ii leetcode | leetcode 40 | backtracking | Facebook Amazon

#Backtracking #Recursion #CombinationSumII #Combination #Sum #LeetCode #Problem40 #Medium #Coding #Programming #Interview #Practice #DataStructure #Algorithm #Java #Preparation #NG #nickode #cct #cook_code_travel

[nagaj]

thanks for a bruteforce solution, it is very poor solution, this is not accepted in interview.

[parwana]

TY, i was searching why Set is not being used by many devs.

[sai]

Why you have removed all your solution explanations from Leetcode's discussion forum?? Those were really helpful.

[PRiyankaSingh-nddn]

Great explaination!
I tried running the same code but it's not giving the correct answer as yours actually. Could you pls tell me where is the lag?

class Solution {
public List<List<Integer>> combinationSum2(int[] candidates, int target) {
Set<List<Integer>> res = new HashSet<>();
Arrays.sort(candidates);
combinationSum2Util(candidates, target, 0, new ArrayList<>(), res);
return new ArrayList(res);
}

public void combinationSum2Util(int[] candidates, int target, int k, List<Integer> list, Set<List<Integer>> res) {
if(target<0) return;
if(target==0) {
res.add(new ArrayList<>(list));
return;
}
for(int i=k; i<candidates.length; i++) {
if(candidates[i]<=target ) {
list.add(candidates[i]);
combinationSum2Util(candidates, target-candidates[i], k+1, list, res);
list.remove(list.size()-1);
}
}
}
}

[vipinamar]

I implemented the same in python but getting a empty list of list returned. If you could find the problem it would be helpful
P.S: I am not using set, I will take of that.

def recombo(arr, start, tot, lis, res):
if tot<0:
return
elif tot==0:
res.append(lis)
for i in range(start, len(arr)):
lis.append(arr[i])
recombo(arr, i+1, tot-arr[i], lis, res)
del lis[-1]
return res
def combo(arr, target):
res=[]
lis=[]
res=recombo (sorted(arr), 0, target, lis, res)
return [res]

[samyaadhikari]

I am doing same but ans is not match. please give the reply
class Solution {
public List<List<Integer>> combinationSum2(int[] candidates, int target) {
Set<List<Integer>> result=new HashSet();
Arrays.sort(candidates);
backtrack(candidates, target, 0, result, new ArrayList());
return new ArrayList(result);

}

void backtrack(int[] can, int target, int index, Set<List<Integer>> ans, List list){

if(target<0)
return;
if(target==0){
ans.add(new ArrayList(list));
}
for(int i=index;i<can.length;i++){
list.add(can[i]);
backtrack(can, target-can[i], index+1, ans, list);
list.remove(list.size()-1);
}
}
}

my output:-[[1, 2, 5], [1, 1, 6], [2, 1, 5], [2, 6], [5, 1, 2], [1, 7], [7, 1], [1, 5, 2], [6, 2]]

[himanshuchodha]

//please tell me where's the issue, i am close to the solution
class Solution {
public List<List<Integer>> combinationSum2(int[] candidates, int target) {
Set<List<Integer>> res = new HashSet<>();

boolean[] visited = new boolean[candidates.length];
Arrays.sort(candidates);

backtracking(res, candidates, visited, target, new ArrayList<>(), 0 );
return new ArrayList<>(res);

}
private void res, int[] candidates, boolean[] visited, int remainingSum, List<Integer> subList, int index){
if(remainingSum==0){
res.add(new ArrayList<>(subList));
}
if(remainingSum<0)
return;
for(int i=index; i<candidates.length; i++){
if(!visited[i]){
subList.add(candidates[i]);
visited[i] = true;
backtracking(res, candidates, visited, remainingSum-candidates[i], subList, index +1);

visited[i] = false;
}
}
}
}