Leetcode 40. Combination Sum II [ Challenge ]

Leetcode 40. Combination Sum II
My contact details

You can practice for coding interview from here

I am Mohammad Fraz , a final year Engineer at DTU and I create content for Coding and technical interviews for FAANG. I explain the intuition to solve Data Structure and Algorithm Questions from leetcode and other platforms. I also cover interview experiences for FAANG and other tech giants. You will also find lectures on the frequently asked interview questions.

[samyakjain]

/*
This is c++ solution [ using technique of keeping previous(pre) boolean variable as taught in the subset (ii) video by Sir ]....I hope it helps you mate ;)
*/

class Solution {
public:
vector<vector<int>> ans;
void fun(int index, vector<int>& nums, int t, vector<int>& temp, bool pre){
if(t==0){
ans.push_back(temp);
return;
}
if(t<0) return;
if(index>=nums.size()) return;

//option 1 excluding
fun(index+1, nums, t, temp, false);

if(index>0 && nums[index]==nums[index-1] && !pre) return;

//option 1 including
temp.push_back(nums[index]);
fun(index+1, nums, t-nums[index], temp, true);
temp.pop_back();
}
vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
sort(candidates.begin(), candidates.end());
vector<int> temp;
fun(0, candidates, target, temp, false);
return ans;
}
};