题解 | JAVA 递归回溯#加起来和为目标值的组合(三)# K-sum [P1]

K-sum 跟这道题 一样的思路，递归回溯的暴力枚举。
唯一不同的就是basecase(i.e. 已经用了k个数时)检查下和是否为n.

时间: O(n^k)
空间: O(k) 栈最高为k。因为用了回溯,栈上每层都是const space.

import java.util.*;

public class Solution {
    ArrayList<ArrayList<Integer>> ans = new ArrayList<>();
  
    public int[][] combination (int k, int n) {
      recurse(0 /* last */, k, n, new ArrayList<>());
      int[][] _ans = new int[ans.size()][];
      
      // convert to int[][]. java是真蛋疼
      for (int i = 0; i < ans.size(); i++) {
        _ans[i] = ans.get(i).stream().mapToInt(x->x).toArray();
      }
      return _ans;
    }
  
    public void recurse(int last, int k, int n, ArrayList<Integer> partial) {
      if (n == 0 && k == 0) {  // found a solution
        ans.add(new ArrayList<>(partial));
        return;
      } else if (n <= 0 || k == 0) // not a solution
        return;
      
      for (int i = last+1; i <= 9; i++) {
        partial.add(i);
        recurse(i, k-1, n-i, partial);
        partial.remove(partial.size()-1);  // 回溯
      }
    }
}