# Combinations

Medium

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

Example:

``````Input:
n = 4, k = 2

Output:

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

## Solution

Backtracking

backtracking模板的应用，这里的条件备选方案不重复，排过序（1,2,3,... n）

``````class Solution {
public List<List<Integer>> combine(int n, int k) {
List<List<Integer>> ans = new ArrayList<>();
if (n == 0 || k == 0) {
return ans;
}
List<Integer> combination = new ArrayList<Integer>();
combineHelper(1, n, k, combination, ans);

return ans;
}

private void combineHelper(int start, int n, int k, List<Integer> combination, List<List<Integer>> ans) {
if (combination.size() == k) {
return;
}
for (int i = start; i <= n; i++) {
combineHelper(i + 1, n, k, combination, ans);
combination.remove(combination.size() - 1);
}
}
}
``````

DFS

``````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<List<Integer>> combine(int n, int k) {
List<List<Integer>> result = new ArrayList<>();

dfs(n, 1, k, new ArrayList<>(), result);

return result;
}

private void dfs(int n, int index, int k, List<Integer> list, List<List<Integer>> result) {
if (list.size() == k) {
return;
}

if (index > n) {
return;
}