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:
If n = 4 and k = 2, a solution is:
[ [2,4], [3,4], [2,3], [1,2], [1,3], [1,4], ]Solution 1: pay attention this is combination(组合) not permutation(排列).
public class Solution {
public List<List<Integer>> combine(int n, int k) {
List<Integer> one=new ArrayList<>();
List<List<Integer>> res=new ArrayList<>();
dfs(1,k,n,one,res);
return res;
}
private void dfs(int i, int k, int n, List<Integer> one, List<List<Integer>> res) {
if (k==one.size()) res.add(new ArrayList<Integer>(one));
else if (i>n) return;
else {
for (int j=i; j<=n; j++) {
one.add(j);
dfs(j+1,k,n,one,res);
one.remove(one.size()-1);
}
}
}
}
没有评论:
发表评论