# 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<List<Integer>> combine(int n, int k) { List<List<Integer>> result = new ArrayList<List<Integer>>(); List<Integer> list = new ArrayList<Integer>(); 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<Integer> list, List<List<Integer>> result) { if (list.size() == k) { result.add(new ArrayList<Integer>(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).