【每日一题】46. Permutations

题目描述

Given a collection of distinct integers, return all possible permutations.

Example:

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

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

题解

典型的递归问题。1、2、 3的全排列，可以分为以1开头，2、 3的全排列；2开头，1，3的全排列；3开头，1,2的全排列。缩小的问题，和原问题相比，只是规模缩小了，问题的求解方式没有发生变化。

对于以1开头的子问题，可以不断缩小，直到剩下一个元素，它的排列时唯一的，然后向上“归”。

自己大脑模拟操作：首先固定1，找到以1开头的所有排列；对于2,3，类似，依次固定2,3，这样我们就找到了一个排列；之后，调换2、3顺序，就找到了另一个排列；然后找以2开头的所有排列，依次类推。

这里，我们定义dfs递归函数，通过参数i表示，当前的排列的下标；当下标超过数组范围时，说明已经找到了一个排列，将这个排列添加到结果数组中；通过不断递归调用，即可得到最终的答案。

class Solution {
public:
    vector<vector<int>> permute(vector<int>& nums) {
        vector<vector<int>> result;
        dfs(nums, result, 0);
        
        return result;
    }
    void dfs(vector<int>& nums, vector<vector<int>>& res, int i){
        if (i >= nums.size()){//终止条件
            res.push_back(nums);
            return;
        }
        for(int j=i; j< nums.size(); j++){
            swap(nums[i], nums[j]);
            dfs(nums, res, i+1);
            swap(nums[i], nums[j]);
        }
    }
};