backtracking/dfs solution with intuition


  • 0
    B
    /**
     * intuition:
     *
     * [10, 1, 2, 7, 6, 1, 5], 8
     *
     * 1. sort the candidates
     * [1, 1, 2, 5, 6, 7, 10], 8
     *
     * 2. total solution =
     * t            new candidates new target
     * 1 + solution([1,2,5,6,7,10], t - 1) +
     * 1 + solution([2,5,6,7,10],   t - 1) +  // duplicate to previous one, remove
     * it
     * 2 + solution([5,6,7,10],     t - 2) +
     * 5 + solution([6,7,10]),      t - 5) +
     * ...
     *
     */
    class Solution {
     public:
      std::vector<std::vector<int>> mResult;
      vector<vector<int>> combinationSum2(const vector<int>& candidates,
                                          int target) {
        auto candi(candidates);
        std::sort(candi.begin(), candi.end());
        std::vector<int> path;
        dfs(candi, path, target);
        return mResult;
      }
    
      void dfs(const vector<int>& candidates, vector<int>& path, int target) {
        // log(candidates, path, target);
        if (target == 0) {
          mResult.push_back(path);
          return;
        } else if (target < 0) {
          return;
        }
        auto candi(candidates);
        while (!candi.empty()) {
          int t = candi[0];
          path.push_back(t);
          // since each one can only be used once, we should remove it
          candi.erase(candi.begin());
          // dfs with new candidates and new target
          dfs(candi, path, target - t);
          // backtracking
          path.pop_back();
          // remove all element that is duplicate to t, see comments in intuition
          // move to next possible sub solution
          candi.erase(std::remove(candi.begin(), candi.end(), t), candi.end());
        }
      }
    }
    

Log in to reply
 

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