首页 > 代码库 > leetcode 77 Combinations ----- java

leetcode 77 Combinations ----- java

2024-08-16 20:38:59   216人阅读

Given two integers n and k, return all possible combinations of k numbers out of 1 ... n.

For example,
If n = 4 and k = 2, a solution is:

[
  [2,4],
  [3,4],
  [2,3],
  [1,2],
  [1,3],
  [1,4],
]

求C(k,n)的所有结果。

 利用回溯（backtracking)来求解释道题是比较简单且效率较高的。

public class Solution {
    public List<List<Integer>> combine(int n, int k) {
        List<List<Integer>> res = new ArrayList<List<Integer>>();
        Con(n,k,0,0,res,new int[k]);
        return res;

    }
    public void Con( int n,int k,int num,int start,List<List<Integer>> res,int[] ans){
        if( num == k){
            ArrayList<Integer> tt = new ArrayList<Integer>();
            for( int i = 0;i<k;i++)
                tt.add(ans[i]);
            res.add(tt);
            return ;
        }
        for( int i = start;i<n;i++){
            ans[num] = i+1;
            Con(n,k,num+1,i+1,res,ans);
        }
        return ;
}
}

 有一点可以修正，就是Con中的for循环，改为

for( int i = start;i<=n-(k-num);i++)

这样可以进一步提高速度。还有就是把res设为全局变量会代码好看一点。。

leetcode 77 Combinations ----- java


联系
我们