Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

组合总和 III #157

Open
louzhedong opened this issue May 22, 2019 · 0 comments
Open

组合总和 III #157

louzhedong opened this issue May 22, 2019 · 0 comments

Comments

@louzhedong
Copy link
Owner

习题

出处 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;
    }


}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees
No one assigned
Labels
None yet
Projects
None yet
Milestone
No milestone
Development

No branches or pull requests
1 participant
@louzhedong