LeetCode 216 Combination Sum III

Find all possible combinations of k numbers that add up to a number n, given that only numbers from 1 to 9 can be used and each combination should be a unique set of numbers.

Example 1:

Input: k = 3, n = 7

Output:

[[1,2,4]]

Example 2:

Input: k = 3, n = 9

Output:

[[1,2,6], [1,3,5], [2,3,4]]

翻譯：從1-9中間選擇k個數，這些數字之和為n，且這k個數字無重複。

使用回溯法，并記錄目前和，如果目前和大于n或者k已經等于3而和不等于n那麼就傳回上一層。

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30

public static List<list <Integer>> combinationSum3(int k, int n) { List<integer> list = new ArrayList</integer><integer>(); List<list <Integer>> result = new ArrayList</list><list <Integer>>(); if (n < k * (k - 1) / 2) return result; result = search(k, n, 1, 0, list, result); return result; }   public static List<List<Integer>> search(int k, int n, int cur, int sum, List<integer> list, List<list <Integer>> result) { if (k == 0) return result; for (int i = cur; i < = 9; i++) { if (sum + i < n) { sum += i; list.add(i); result = search(k - 1, n, i + 1, sum, list, result); list.remove(list.size() - 1); sum -= i; } else if (sum + i == n && k == 1) { list.add(i); result.add(new ArrayList<Integer>(list)); list.remove(list.size() - 1); } else break; } return result; }