leetcode77-组合

原题

给定两个整数 n 和 k,返回 1 ... n 中所有可能的 k 个数的组合。

示例:

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

解法

思想

leetcode非常多这种类似的题目,例如leetcode39-组合总和leetcode40-组合总和II。多做一些题目心里就有模板了,这道题可以剪枝(根据要求的数量,很多情况搜的是不必要的),但我没剪。

代码

class Solution {
    List<List<Integer>> ans = new ArrayList<>();
    int k;
    int n;
    public List<List<Integer>> combine(int n, int k) {
        this.k = k;
        this.n = n;
        List<Integer> list = new ArrayList<>();
        dfs(list,1);        
        return ans;
    }

    public void dfs(List<Integer> list,int min){
        for(int i = min ; i <= n; i++){
            List<Integer> copy = new ArrayList<>(list);
            copy.add(i);
            if(copy.size() == k) {
                ans.add(copy);
                continue;
            }
            dfs(copy,i+1);
        }
    }
}

原创文章,作者:彭晨涛,如若转载,请注明出处:https://www.codetool.top/article/leetcode77-%e7%bb%84%e5%90%88/

发表评论

电子邮件地址不会被公开。