nikunjsoni

40

Jul 14th, 2021
93
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. class Solution {
  2. public:
  3.     vector<vector<int>> res;
  4.     vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
  5.         sort(candidates.begin(), candidates.end());
  6.         vector<int> path;
  7.         backtrack(candidates, target, path, 0);
  8.         return res;
  9.     }
  10.    
  11.     void backtrack(vector<int> &cand, int target, vector<int> &path, int idx){
  12.         if(target == 0){
  13.             res.push_back(path);
  14.             return;
  15.         }
  16.         if(idx >= cand.size())
  17.             return;
  18.         for(int i=idx; i<cand.size(); i++){
  19.             if(i>idx && cand[i-1] == cand[i])
  20.                 continue;
  21.             if(cand[i] <= target){
  22.                 path.push_back(cand[i]);
  23.                 backtrack(cand, target-cand[i], path, i+1);
  24.                 path.pop_back();
  25.             }
  26.         }
  27.     }
  28. };
RAW Paste Data