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], ]
这类组合问题的思路常见的一个办法就是递归。
如果show（在结果里面show）那么该怎么处理，
如果not show (不出现在结果里面）该怎么处理。
void C(vector<int> array, int start, int k, vector<int> result, int index, vector<vector<int>>* finalvec) { if (index == k) //found one { finalvec->push_back(result); return; } if (start<array.size()) { //show result[index] = array[start]; C(array, start + 1, k, result, index + 1, finalvec); C(array, start + 1, k, result, index, finalvec); } } vector<vector<int> > combine(int n, int k) { vector<int> array(n); vector<vector<int>> finalresult; for (int i = 1; i <= n; i++) { array[i - 1] = i; } vector<int> result(k); int start = 0; int index = 0; C(array, start, k, result, index, &finalresult); return finalresult; }
类似的另外一个题目是 skip digits encoding, 比如说某个国家的人不喜欢4， 那么在所有的number里都不能出现4， 现在给定一个数 1876, 应该对应于real life的哪个数。
思路：
100～999中有多个数不包含digits 4， 因为是三位数，每个位置上出现的数字都是独立的，因为不能是4， 那每一位上不出现的可能性是C（9，1）
那么正好在 100～999中 C(9,1)* C(9,1)*C(9,1)
同样道理 10～99 中C(9,1)*c(9,1)
0~9 C(9,1)
int convert(int magic, int hatedigit) { int outnumber = 0; int basep = 9; int p = 1; while (magic>0) { int digits = magic % 10; if (digits> hatedigit) outnumber += (digits - 1)* p; else outnumber += digits*p; p *= 9; magic = magic / 10; } return outnumber; }
原文：http://www.cnblogs.com/oceancloud/p/3540041.html