全排列-46

Given an array nums of distinct integers, return all the possible permutations. You can return the answer in any order.

示例 1：

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

示例 2：

Input: nums = [0,1]
Output: [[0,1],[1,0]]

示例 3：

Input: nums = [1]
Output: [[1]]

提示：

• 1 ≤ nums.length ≤ 6
• -10 ≤ nums[i] ≤ 10
• All the integers of nums are unique.

思路

本题可构建一棵树，如下图所示：

采用一次DFS即可得到答案。

DFS是基于递归，本题的终止条件是：当前层数等于输入列表的长度时，终止递归。

代码

class Solution {
public:
    void dfs(vector<int>& nums, vector< vector<int> >& ans, int level, bool visited[], vector<int>& path) {
        // 1. Exit condition
        if( nums.size() == level ) {
            ans.push_back( path );
            return;
        }
        // 2. Walk every node that not visited
        for(int i = 0; i < nums.size(); i++) {
            int node = nums[i];
            if( !visited[i] ) {
                visited[i] = true;
                path.push_back( node );
                dfs(nums, ans, level+1, visited, path);
                path.pop_back();
                visited[i] = false;
            }
        }
    }
    vector<vector<int>> permute(vector<int>& nums) {
        vector< vector<int> > answer;
        if( nums.size() == 0 )   return answer;
        if( nums.size() == 1 ) {
            answer.push_back(nums);
            return answer;
        }
        bool visited[ nums.size() ];
        for(int i = 0; i < nums.size(); i++) 
            visited[i] = false;
        vector<int> path;
        dfs( nums, answer, 0, visited, path );
        return answer;
    }
};