题解 | JAVA #加起来和为目标值的组合(二)# [P0-T2]

正常暴力枚举(递归+回溯)

时间: O(n!)
空间: O(n)

import java.util.*;

public class Solution {
  final ArrayList<ArrayList<Integer>> ans = new ArrayList<>();
  
  public ArrayList<ArrayList<Integer>> combinationSum2(int[] num, int target) {
    Arrays.sort(num);
    recurse(num, target, 0, new ArrayList<Integer>());
    return ans;
  }
  
  private void recurse(int[] num, int target, 
                       int start, ArrayList<Integer> prev) {
    // basecase-1
    if (target == 0 && prev.size() > 0) {
      ans.add(new ArrayList<>(prev));
      return;  // array is increasing, so can stop here 
    }
    
    int last = -1;
    for (int i = start; i < num.length; i++) {
      int cur = num[i];
      if (cur == last) continue;  // skip duplicates
      if (cur > target) return;   // basecase-2, short cut, array is increasing
      
      last = cur;
      prev.add(cur);
      recurse(num, target-cur, i+1, prev);
      prev.remove(prev.size()-1);  // backtrack
    }
  }
}