Combinations
最后更新于：2022-04-02 01:12:27
# Combinations
### Source
- leetcode: [Combinations | LeetCode OJ](https://leetcode.com/problems/combinations/)
- lintcode: [(152) Combinations](http://www.lintcode.com/en/problem/combinations/)
~~~
Given two integers n and k,
return all possible combinations of k numbers out of 1 ... n.
Example
For example,
If n = 4 and k = 2, a solution is:
[[2,4],[3,4],[2,3],[1,2],[1,3],[1,4]]
~~~
### 题解
套用 [Permutations](http://algorithm.yuanbin.me/zh-cn/exhaustive_search/permutations.html) 模板。
### Java
~~~
public class Solution {
/**
* @param n: Given the range of numbers
* @param k: Given the numbers of combinations
* @return: All the combinations of k numbers out of 1..n
*/
public List> combine(int n, int k) {
List> result = new ArrayList>();
List list = new ArrayList();
if (n <= 0 || k <= 0) return result;
helper(n, k, 1, list, result);
return result;
}
private void helper(int n, int k, int pos,
List list, List> result) {
if (list.size() == k) {
result.add(new ArrayList(list));
return;
}
for (int i = pos; i <= n; i++) {
list.add(i);
helper(n, k, i + 1, list, result);
list.remove(list.size() - 1);
}
}
}
~~~
### 源码分析
注意递归`helper(n, k, i + 1, list, result);`中的`i + 1`，不是`pos + 1`。
### 复杂度分析
状态数 Cn2C_n^2Cn2, 每组解有两个元素，故时间复杂度应为 O(n2)O(n^2)O(n2). list 只保留最多两个元素，空间复杂度 O(1)O(1)O(1).
';