40 - Combination Sum II

 JAVA

• class Solution {
      private List<List<Integer>> ans = new ArrayList<>();
      private List<Integer> t = new ArrayList<>();
      private int[] candidates;
  
      public List<List<Integer>> combinationSum2(int[] candidates, int target) {
          Arrays.sort(candidates);
          this.candidates = candidates;
          dfs(0, target);
          return ans;
      }
  
      private void dfs(int i, int s) {
          if (s == 0) {
              ans.add(new ArrayList<>(t));
              return;
          }
          if (i >= candidates.length || s < candidates[i]) {
              return;
          }
          for (int j = i; j < candidates.length; ++j) {
              if (j > i && candidates[j] == candidates[j - 1]) {
                  continue;
              }
              t.add(candidates[j]);
              dfs(j + 1, s - candidates[j]);
              t.remove(t.size() - 1);
          }
      }
  }

C++

• class Solution {
  public:
      vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
          sort(candidates.begin(), candidates.end());
          vector<vector<int>> ans;
          vector<int> t;
          function<void(int, int)> dfs = [&](int i, int s) {
              if (s == 0) {
                  ans.emplace_back(t);
                  return;
              }
              if (i >= candidates.size() || s < candidates[i]) {
                  return;
              }
              for (int j = i; j < candidates.size(); ++j) {
                  if (j > i && candidates[j] == candidates[j - 1]) {
                      continue;
                  }
                  t.emplace_back(candidates[j]);
                  dfs(j + 1, s - candidates[j]);
                  t.pop_back();
              }
          };
          dfs(0, target);
          return ans;
      }
  };