组合总和 III

[louzhedong]

习题

出处 LeetCode 算法第216题

找出所有相加之和为 n 的 k 个数的组合**。**组合中只允许含有 1 - 9 的正整数，并且每种组合中不存在重复的数字。

说明：

• 所有数字都是正整数。
• 解集不能包含重复的组合。

示例 1:

输入: k = 3, n = 7
输出: [[1,2,4]]

示例 2:

输入: k = 3, n = 9
输出: [[1,2,6], [1,3,5], [2,3,4]]

思路

采用DFS的方法遍历所有组合

解答

JavaScript

/**
 * @param {number} k
 * @param {number} n
 * @return {number[][]}
 */
var combinationSum3 = function (k, n) {
  var result = [];
  var temp = [];
  for (var i = 1; i <= 9; i++) {
    temp.push(i);
    helper(result, temp, i, k, n);
    temp.pop();
  }

  return result;
};

function copy(array) {
  var res = [];
  for (var i = 0, len = array.length; i < len; i++) {
    res.push(array[i]);
  }
  return res;
}
function sum(array) {
  return array.reduce(function (prev, curr) {
    return prev + curr;
  })
}

function helper(result, temp, flag, k, n) {
  if (sum(temp) == n && temp.length == k) {
    result.push(copy(temp));
  }
  for (var i = flag + 1; i <= 9; i++) {
    temp.push(i);
    helper(result, temp, i, k, n);
    temp.pop();
  }
}

Java

class Solution {
    public List<List<Integer>> combinationSum3(int k, int n) {
        List<List<Integer>> result = new ArrayList<>();
        List<Integer> temp = new ArrayList<>();

        for (int i = 1; i <= 9; i++) {
            temp.add(i);
            helper(result, temp, i, k, n);
            temp.remove(temp.size() - 1);
        }
        return result;
    }

    private void helper(List<List<Integer>> result, List<Integer> temp, int flag, int k, int n) {
        if (sum(temp) == n && temp.size() == k) {
            result.add(copy(temp));
        }
        for (int i = flag + 1; i <= 9; i++) {
            temp.add(i);
            helper(result, temp, i, k, n);
            temp.remove(temp.size() - 1);
        }
    }

    private List<Integer> copy(List<Integer> array) {
        List<Integer> result = new ArrayList<>();
        array.forEach(i-> {
            result.add(i);
        });
        return result;
    }

    private Integer sum(List<Integer> array) {
        int sum = 0, length = array.size();
        for (int i = 0; i < length; i++) {
            sum += array.get(i);
        }
        return sum;
    }


}