#include "s0040_combination_sum_ii.hpp"

void combinationSum2DFS(vector<int> &candidates, int target, int startIndex,
                        vector<int> &path, int sum, vector<bool> &used,
                        vector<vector<int>> &result) {
  // 结束条件：总和等于 target 。不存在总和大于 target 的情况，因为已经被剪枝了
  if (sum == target) {
    result.push_back(path);
    return;
  }

  // 开始迭代
  int size = candidates.size();
  for (int i = startIndex; i < size; ++i) {
    // 剪枝，当现在节点的 sum 已经超过了 target，就没必要继续迭代了
    if (sum + candidates[i] > target) break;
    // 剪枝，但保留树枝重复的情况
    if (i > 0 && candidates[i] == candidates[i - 1] && used[i - 1] == false)
      continue;
    path.push_back(candidates[i]);
    used[i] = true;
    combinationSum2DFS(candidates, target, i + 1, path, sum + candidates[i],
                       used, result);
    used[i] = false;
    path.pop_back();
  }
}

vector<vector<int>> S0040::combinationSum2(vector<int> &candidates,
                                           int target) {
  // 对 candidates 进行升序排序，这是为了进行剪枝
  sort(candidates.begin(), candidates.end());
  // 初始化
  vector<int> path{};
  vector<vector<int>> result{};
  vector<bool> used(candidates.size(), false);
  combinationSum2DFS(candidates, target, 0, path, 0, used, result);
  return result;
}