Leetcode.46.Permutations

题目

给定一个没有重复数字的数字序列, 输出这写数字的全排列组合.

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

思路

这种全排列的问题最直接的思路就是递归.

通过对已经排列的数字进行标记, 来进行循环.

void recrution(vector<int> &nums, int &visit, vector<int> &path, vector<vector<int>> &result) {
  if (nums.size() == path.size()) {
      // 组装成功
      result.push_back(path);
      return;
  }

  for (int i = 0;i < nums.size();i++) {
    int isWillVisit = (visit ^ (1<<i)) & (1 <<i);
    if (isWillVisit) {
        path.push_back(nums[i]);
        visit |= (1 << i);
        recrution(nums, visit, path, result);
        visit ^= (1 << i);
        path.pop_back();
    }
  }
}

// 递归
vector<vector<int>> permute(vector<int>& nums) {
    vector<vector<int>> result;
    vector<bool> visited(nums.size(), 0);
    int visit = 0; 
    vector<int> path;
    recrution(nums, visit, path, result);
    return result;
}

总结

运用位运算节约标记成本.