这两天去了北京故宫博物院和八达岭长城，真是人挤人，公交车上撸了一道Combinations，手机登陆leetcode写代码总是存在奇怪的中文编码的问题，可以选择使用app黑客键盘，编码相对舒服一丢丢，如果还是存在编码问题就一行一行的删空格吧。
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], ]
相当于是把C(n,k)的所有情况给列出来。
第一个想到的办法还是利用递归，每次插入一个数，然后传递给下一次递归状态，整体还是比较简单的。
class Solution {public:vector<vector<int>> combine(int n, int k) {vector<vector<int>> res;vector<int> tmp;go(res, tmp, 0, 1, k, n); return res;}void go(vector<vector<int>>&res, vector<int> &now, int nindex, int num, int k, int n){if (num == k) {for (int i = nindex; i<n; i++){now.push_back(i + 1);res.push_back(now); now.pop_back();}}else {for (int i = nindex; i<n - k + num; i++){now.push_back(i + 1);go(res, now, i + 1, num + 1, k, n);now.pop_back();}}}};++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
Given a set of distinct integers, nums, return all possible subsets (the power set).
Note: The solution set must not contain duplicate subsets.
Example:
Input: nums = [1,2,3] Output: [[3],[1],[2],[1,2,3],[1,3],[2,3],[1,2],[] ]
求一个集合的子集，集合中的数字保证是不重复的。
想到的办法还是递归，跟上一题思路类似的递归
class Solution {
public:vector<vector<int>> subsets(vector<int>& nums) {//sort(nums.begin(), nums.end());vector<int> tmp;vector<vector<int>> res;res.push_back(tmp);for(int i=1;i<=nums.size();i++)go(res, nums, tmp, 0, i, 0, nums.size());return res;}void go(vector<vector<int>> &res, vector<int> nums, vector<int> &local, int now_index, int K_num, int size, int n){if (K_num == n + 1) return;if (K_num == 1){for (int i = now_index; i<n; i++){local.push_back(nums[i]);res.push_back(local);local.pop_back();}return;}else{for (int i = now_index; i <= n - K_num; i++){local.push_back(nums[i]);go(res, nums, local, i + 1, K_num - 1, size + 1, n);local.pop_back();}}}
};然后看完discuss发现了一个利用位运算计算该问题的办法，看完代码可以说是......豁然开朗
让我们来看看这个巧妙的思路：
class Solution {
public:vector<vector<int>> subsets(vector<int>& nums) { int cnt = 0;int n = nums.size();int sub = pow(2, n);vector<vector<int>> result(sub, vector<int>());for(int i = 0; i < n; i ++){for(int j = 0; j < sub; j++){if(j>>i & 1){result[j].push_back(nums[i]);}}}return result;}
};思路可以说是相当简单了，
假设我们的集合nums为{1，2，3，5，8，13，21}
我们可以利用位图来表示该集合，这个位图即为7位的二进制数 111 1111
比如这个nums集合的子集为{1，2，3}，所对应的位图即为 111 0000
如果为空集即为 000 0000
而所有子集的情况，即为 000 0000 - 111 1111的所有二进制数！
if(j>>i &1) 这句话的涵义是判断所有二进制数上的第i位是不是1