I solved the problem using Inclusion Exclusion. But it gives TLE 172/176 passed. I want to solve it with Inclusion Exclusion not iteration over the array using for loop.
class Solution {
public:
void solve(vector& candidates, vector<vector>&ans,vector&temp,int target, int index){
// BC
if(target==0){
ans.push_back(temp);
return;
}
if(index>=candidates.size() || target<0){
return;
}
// exclusion
solve(candidates,ans,temp,target,index+1);
// Inclussion
temp.push_back(candidates[index]);
solve(candidates,ans,temp,target-candidates[index],index+1);
// backtrack
temp.pop_back();
}
vector<vector> combinationSum2(vector& candidates, int target) {
vector<vector>ans;
vectortemp;
sort(candidates.begin(),candidates.end());
solve(candidates,ans,temp,target,0);
sort(ans.begin(),ans.end());
auto last=unique(ans.begin(),ans.end());
ans.erase(last,ans.end());
return ans;
}
};
Time Limit Exceeded
172 / 176 testcases passed
Last Executed Input
Use Testcase
candidates =
[1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1]
target = 30
Mohit Kumar is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.