给定一个 没有重复 数字的序列，返回其所有可能的全排列。

  1. 输入: [1,2,3]
  2. 输出:
  3. [
  4.   [1,2,3],
  5.   [1,3,2],
  6.   [2,1,3],
  7.   [2,3,1],
  8.   [3,1,2],
  9.   [3,2,1]
  10. ]

c plus

  • 回溯
    需要重点理解回溯算法
    题解

    1. class Solution {
    2. public:
    3.   vector<vector<int>> res;
    4.   vector<vector<int>> permute(vector<int>& nums) {
    5.      if (nums.size() <= 1) {
    6.           res.push_back(nums);
    7.           return res;
    8.      }
    10.      vector<int> cur;
    11.      vector<bool> used(nums.size(), false);
    12.      helper(cur, used, nums);
    13.      return res;
    14.   }
    15.   void  helper(vector<int>& cur, vector<bool>& used, vector<int>& nums) {
    16.       if (cur.size() == nums.size()) {
    17.           return res.push_back(cur);
    18.       }
    19.       for (int i = 0; i < nums.size(); ++i) {
    20.           if (!used[i]){
    21.               used[i] = true;
    22.               cur.push_back(nums[i]);
    23.               helper(cur, used, nums);
    24.               used[i] = false;
    25.               cur.pop_back();
    26.           }
    27.       }
    28.   } 
    29. };

%E7%BB%99%E5%AE%9A%E4%B8%80%E4%B8%AA%20%E6%B2%A1%E6%9C%89%E9%87%8D%E5%A4%8D%20%E6%95%B0%E5%AD%97%E7%9A%84%E5%BA%8F%E5%88%97%EF%BC%8C%E8%BF%94%E5%9B%9E%E5%85%B6%E6%89%80%E6%9C%89%E5%8F%AF%E8%83%BD%E7%9A%84%E5%85%A8%E6%8E%92%E5%88%97%E3%80%82%0A%60%60%60%0A%E8%BE%93%E5%85%A5%3A%20%5B1%2C2%2C3%5D%0A%E8%BE%93%E5%87%BA%3A%0A%5B%0A%20%20%5B1%2C2%2C3%5D%2C%0A%20%20%5B1%2C3%2C2%5D%2C%0A%20%20%5B2%2C1%2C3%5D%2C%0A%20%20%5B2%2C3%2C1%5D%2C%0A%20%20%5B3%2C1%2C2%5D%2C%0A%20%20%5B3%2C2%2C1%5D%0A%5D%0A%60%60%60%0A%23%23%23%20c%20plus%0A%0A%20%20%0A%20%E5%9B%9E%E6%BA%AF%0A%20%20%E9%9C%80%E8%A6%81%E9%87%8D%E7%82%B9%E7%90%86%E8%A7%A3%E5%9B%9E%E6%BA%AF%E7%AE%97%E6%B3%95%0A%0A%20%20%5B%E9%A2%98%E8%A7%A3%5D(https%3A%2F%2Fleetcode-cn.com%2Fproblems%2Fpermutations%2Fsolution%2Fhui-su-suan-fa-python-dai-ma-java-dai-ma-by-liweiw%2F)%0A%60%60%60c%0Aclass%20Solution%20%7B%0Apublic%3A%0A%20%20%20%20vector%3Cvector%3Cint%3E%3E%20res%3B%0A%20%20%20%20vector%3Cvector%3Cint%3E%3E%20permute(vector%3Cint%3E%26%20nums)%20%7B%0A%20%20%20%20%20%20%20if%20(nums.size()%20%3C%3D%201)%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20res.push_back(nums)%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20return%20res%3B%0A%20%20%20%20%20%20%20%7D%0A%20%20%20%20%20%0A%20%20%20%20%20%20%20vector%3Cint%3E%20cur%3B%0A%20%20%20%20%20%20%20vector%3Cbool%3E%20used(nums.size()%2C%20false)%3B%0A%20%20%20%20%20%20%20helper(cur%2C%20used%2C%20nums)%3B%0A%20%20%20%20%20%20%20return%20res%3B%0A%20%20%20%20%7D%0A%20%20%20%20void%20%20helper(vector%3Cint%3E%26%20cur%2C%20vector%3Cbool%3E%26%20used%2C%20vector%3Cint%3E%26%20nums)%20%7B%0A%20%20%20%20%20%20%20%20if%20(cur.size()%20%3D%3D%20nums.size())%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20return%20res.push_back(cur)%3B%0A%20%20%20%20%20%20%20%20%7D%0A%20%20%20%20%20%20%20%20for%20(int%20i%20%3D%200%3B%20i%20%3C%20nums.size()%3B%20%2B%2Bi)%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20if%20(!used%5Bi%5D)%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20used%5Bi%5D%20%3D%20true%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20cur.push_back(nums%5Bi%5D)%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20helper(cur%2C%20used%2C%20nums)%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20used%5Bi%5D%20%3D%20false%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20cur.pop_back()%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20%7D%0A%20%20%20%20%20%20%20%20%7D%0A%20%20%20%20%7D%20%0A%7D%3B%0A%0A%60%60%60%0A%0A%20%20*%0A