力扣46. 全排列

Problem: 46. 全排列

题目描述

思路及解法

回溯可以理解为是在对一个多叉树的操作

1.回溯结束条件：当决策路径的长度等于nums数组的长度时，将当前的结果添加到二维结果集res中；
2.每一次决策的选择处理：每次我们先查找当前决策路径中是否存在nums[i],若存在则跳过，直至不存在；
3.先将当前的路径上的值添加到决策路径中，并开始下一层决策，最后将当前决策从决策路径中去除；

复杂度

时间复杂度:

$O(N\times N!)$;其中$N$为数组nums的长度

空间复杂度:

$O(N)$

Code

class Solution {
    //Recode the result
    vector> res;
public:
    /**
     * Full permutation
     * 
     * @param nums An array to be fully arranged
     * @return vector>
     */
    vector> permute(vector &nums) {
        vector track;
        backtrack(nums, track);
        return res;
    }

    /**
     * Implementation of backtracking function
     *
     * @param nums An array to be fully arranged
     * @param track Selection path
     */
    void backtrack(vector &nums, vector track) {
        if (track.size() == nums.size()) {
            res.push_back(track);
            return;
        }

        for (int i = 0; i < nums.size(); ++i) {
            if (find(track.begin(), track.end(), nums[i]) != track.end()) {
                continue;
            }
            //Chose
            track.push_back(nums[i]);
            backtrack(nums, track);
            track.pop_back();
        }
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40