package question;

import java.util.LinkedList;
import java.util.List;

public class Question216 {
 List<List<Integer>> res = new LinkedList<>();

 public List<List<Integer>> combinationSum3(int k, int n) {
 List<Integer> list = new LinkedList<>();
 huiSu(list, k, n, 0, 1);
 return res;
 }

 public void huiSu(List<Integer> list, int k, int n, int sum, int i) {
 if (k <= list.size()) {
 if (sum == n) {
 res.add(new LinkedList<>(list));
 }
 return;
 }
 if (sum >= n) return;
 for (; i < 10; i++) {
 list.add(i);
 sum += i;
 huiSu(list, k, n, sum, i + 1);
 sum -= i;
 list.remove(list.size() - 1);
 }
 }
}