c++ backtracking (13 ms)


  • 0
    class Solution {
      public:
        void bt(int comb_sum, int start, int target, vector<int>& tmp, const vector<int>& cand, vector<vector<int>>& ans) {
          if (comb_sum == target) {
            ans.push_back(tmp);
            return;
          }
          if (comb_sum > target) return;
          for (int i = start; i < cand.size(); ++i) {
            if (comb_sum + cand[i] > target) continue;
            tmp.push_back(cand[i]);
            bt(comb_sum + cand[i], i, target, tmp, cand, ans);
            tmp.pop_back();
          }
        }
        vector<vector<int>> combinationSum(vector<int>& candidate, int target) {
          vector<vector<int>> ans;
          vector<int> tmp;
          bt(0, 0, target, tmp, candidate, ans);
          return ans;
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.