nikunjsoni

216

Jul 14th, 2021
86
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. class Solution {
  2. public:
  3.     vector<int> nums = {1,2,3,4,5,6,7,8,9};
  4.     vector<vector<int>> ans;
  5.     //vector<int> vis(nums.size(),-1);
  6.     //nsf --> number/candidate taken so far
  7.     //ssf --> sum so far
  8.     //fn --> final no of candidates/number to use
  9.     //fs -->final sum
  10.    
  11.     void backtrack(vector<int> &temp, int nsf, int ssf, int &fn, int &fs, int start){
  12.         if(nsf==fn && ssf==fs){
  13.             ans.push_back(temp);
  14.             return;
  15.         }
  16.         else if(nsf>fn || ssf>fs){
  17.             return;
  18.         }
  19.         for(int i=start;i<nums.size();i++){
  20.             if(ssf+nums[i]<=fs && nsf+1<=fn){
  21.                 temp.push_back(nums[i]);
  22.                 backtrack(temp, nsf+1, ssf+nums[i], fn, fs,i+1);
  23.                 temp.pop_back();
  24.             }
  25.         }
  26.     }
  27.    
  28.     vector<vector<int>> combinationSum3(int k, int n) {
  29.         ios_base::sync_with_stdio(false);
  30.         cin.tie(NULL);
  31.         vector<int> temp;
  32.         backtrack(temp, 0, 0, k, n, 0);
  33.         return ans;
  34.     }
  35. };
RAW Paste Data