nikunjsoni

39

Jul 14th, 2021
103
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>> combinationSum(vector<int>& candidates, int target) {
  5.         vector<int> path;
  6.         sort(candidates.rbegin(), candidates.rend());
  7.         backtrack(candidates, target, 0, path);
  8.         return res;
  9.     }
  10.    
  11.     void backtrack(vector<int> &cand, int sum, int idx, vector<int> &path){
  12.         if(sum == 0){
  13.             res.push_back(path);
  14.             return;
  15.         }
  16.         for(int i=idx; i<cand.size(); i++){
  17.             if(sum-cand[i] >= 0){
  18.                 path.push_back(cand[i]);
  19.                 sum-=cand[i];
  20.                 backtrack(cand, sum, i, path);
  21.                 path.pop_back();
  22.                 sum+=cand[i];
  23.             }
  24.         }
  25.     }
  26.    
  27. };
RAW Paste Data