题目

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.

Note:

  • All numbers will be positive integers.
  • The solution set must not contain duplicate combinations.

Example 1:

  1. Input: k = 3, n = 7
  2. Output: [[1,2,4]]

Example 2:

  1. Input: k = 3, n = 9
  2. Output: [[1,2,6], [1,3,5], [2,3,4]]

题意

从1-9这9个数中选取k个数，使其之和正好为n，求出所有这样的组合。

思路

排列组合题，使用回溯法很容易求解。

代码实现

Java

  1. class Solution {
  2.     public List<List<Integer>> combinationSum3(int k, int n) {
  3.         List<List<Integer>> ans = new ArrayList<>();
  4.         dfs(n, k, 0, 1, new ArrayList<>(), ans);
  5.         return ans;
  6.     }
  8.     private void dfs(int n, int k, int sum, int start, List<Integer> temp, List<List<Integer>> ans) {
  9.         if (temp.size() == k && sum == n) {
  10.             ans.add(new ArrayList<>(temp));
  11.             return;
  12.         }
  14.         if (temp.size() >= k || sum >= n) {
  15.             return;
  16.         }
  18.         for (int i = start; i <= 9; i++) {
  19.             temp.add(i);
  20.             dfs(n, k, sum + i, i + 1, temp, ans);
  21.             temp.remove(temp.size() - 1);
  22.         }
  23.     }
  24. }

JavaScript

  1. /**
  2.  * @param {number} k
  3.  * @param {number} n
  4.  * @return {number[][]}
  5.  */
  6. var combinationSum3 = function (k, n) {
  7.   let ans = []
  8.   dfs(0, [], 1, ans, k, n)
  9.   return ans
  10. }
  12. let dfs = function (sum, tmp, begin, ans, k, n) {
  13.   if (tmp.length === k && sum === n) {
  14.     return ans.push([...tmp])
  15.   }
  17.   if (tmp.length >= k || sum >= n) {
  18.     return
  19.   }
  21.   for (let i = begin; i <= 9; i++) {
  22.     tmp.push(i)
  23.     dfs(sum + i, tmp, i + 1, ans, k, n)
  24.     tmp.pop()
  25.   }
  26. }