LeetCode-Combinations

Combinations

##题目

####Combinations

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

##解题思路
该题用到的还是N-Queens中的方法：用一个循环递归处理子问题。实现的代码跟Combination Sum非常类似而且更加简练，因为不用考虑重复元素的情况，而且元素只要到了k个就可以返回一个结果.

##算法代码
代码采用JAVA实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public class Solution {
    public ArrayList<ArrayList<Integer>> combine(int n, int k) {  
        ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();  
        if(n<=0 || n<k)  
            return res;  
        helper(n,k,1,new ArrayList<Integer>(), res);  
        return res;  
    }  
    private void helper(int n, int k, int start, ArrayList<Integer> item, ArrayList<ArrayList<Integer>> res)  
    {  
        if(item.size()==k)  
        {  
            res.add(new ArrayList<Integer>(item));  
            return;  
        }  
        for(int i=start;i<=n;i++)  
        {  
            item.add(i);  
            helper(n,k,i+1,item,res);  
            item.remove(item.size()-1);  
        }  
    }
}

Comments

▲