Leetcode.78.Subsets

题目

给定一个整形数组, 输出所有可能的子数组.

Input: [1,2,3]
Output: [[],[1],[2],[3],[1,2],[1,3],[2,3],[1,2,3]]

思路1

传统方法, 递归

从0个到n个子集依次递归.

void getCombinations(vector<vector<int>>& result, vector<int>& nums, vector<int>& temp, int index, int count) {
    if (count == 0) {
        result.push_back(temp);
        return;
    }

    for (int i = index; i < nums.size(); i++) {
        temp.push_back(nums[i]);
        getCombinations(result, nums, temp, i+1, count-1);
        temp.pop_back();
    }
}

vector<vector<int>> subsets(vector<int>& nums) {
    vector<vector<int>> result;
    vector<int> temp;

    for (int count = 0; count <= nums.size(); count++) {
        getCombinations(result, nums, temp, 0, count);
    }
    return result;
}   

思路2

借助2进制的思想, 010101刚好表示是否输出该元素, 从0到2的n次方遍历, 遇到1就输出该元素.

vector<vector<int>> subsets2(vector<int>& nums) {
  vector<vector<int>> result;
  int n = nums.size();
  for(int i = 0;i < (1 << n);i++) {
      vector<int> temp;
      for (int j = 0; j < n;j++) {
          if(i & (1<<j)) {
              temp.push_back(nums[j]);
          }
      }
      result.push_back(temp);
  }
  return result;
}

总结

这种问题最直接的方法就是递归, 一定要熟练掌握递归要领.

2进制方法往往可以比较巧妙处理问题.