content: // https://leetcode.com/problems/combination-sum-ii
  // T: O(2^N)
  // S: O(N)
  
  import java.util.ArrayList;
  import java.util.Arrays;
  import java.util.LinkedList;
  import java.util.List;
  
  public class CombinationSumII {
      public List<List<Integer>> combinationSum2(int[] candidates, int target) {
          List<List<Integer>> results = new ArrayList<>();
          LinkedList<Integer> comb = new LinkedList<>();
          Arrays.sort(candidates);
          backtrack(candidates, comb, target, 0, results);
          return results;
      }
  
      private void backtrack(int[] candidates, LinkedList<Integer> comb,
                             int remain, int curr,
                             List<List<Integer>> results) {
          if (remain == 0) {
              results.add(new ArrayList<Integer>(comb));
              return;
          }
  
          for (int nextCurr = curr; nextCurr < candidates.length; ++nextCurr) {
              if (nextCurr > curr && candidates[nextCurr] == candidates[nextCurr - 1])
                  continue;
  
              int pick = candidates[nextCurr];
              if (remain - pick < 0) break;
  
              comb.addLast(pick);
              backtrack(candidates, comb, remain - pick, nextCurr + 1, results);
              comb.removeLast();
          }
      }
  }
  