首页 > 代码库 > leetcode--Combinations

leetcode--Combinations

2024-07-07 09:08:35   229人阅读

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],
]

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
public class Solution {
    /**This code is an implemenatation of bfs idea.<br>
     * @author Averill Zheng
     * @version 2014-06-05
     * @since JDK 1.7
     */
    public List<List<Integer>> combine(int n, int k) {
        List<List<Integer> > combinations = new ArrayList<List<Integer> >();
        if(k > 0){
            for(int i = 0; i < n; ++i){
                List<Integer> aList = new ArrayList<Integer>();
                aList.add(i + 1);
                combinations.add(aList);
            }
            if(k > 1){
                for(int j = 1; j < k; ++j){ //j denotes the number of integer in each list
                    List<List<Integer>> temp = new ArrayList<List<Integer> >();
                    int length = combinations.size();
                    for(int l = 0; l < length; ++l){
                        List<Integer> aList = combinations.get(l);
                        int lastNumber = aList.get(j - 1);
                        if(n - lastNumber >= k - j){ // has enough number to get the k combinations
                            for(int m = lastNumber + 1; m <= n; ++m){
                                List<Integer> newList = new ArrayList<Integer>();
                                newList.addAll(aList);
                                newList.add(m);
                                temp.add(newList);
                            }
                        }
                    }
                    combinations = temp;
                }
            }
        }  
        return combinations;   
    }
}

　　


联系
我们