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以内的正整数，每个数有放入与不放入两种选择=>带回溯的递归
class Solution { public: vector<vector<int>> combine(int n, int k) { vector<vector<int>> result; vector<int> pre; dfs(result,pre,n,k,1); return result; } void dfs( vector<vector<int>> &result, vector<int> pre, int n, int k, int depth) { if(depth > n) return; pre.push_back(depth); if(pre.size() < k) { dfs(result,pre,n,k,depth+1); } else { result.push_back(pre); } pre.pop_back(); dfs(result,pre,n,k,depth+1); } };
77. Combinations (Recursion, DP)
原文：http://www.cnblogs.com/qionglouyuyu/p/4855303.html