1
2

输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

1
2

输入：nums = [0,1]
输出：[[0,1],[1,0]]

1
2

输入：nums = [1]
输出：[[1]]

 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
41
42

class Solution {
    vector<vector<int>> result;
public:
    /*
    * ## 解题思路
    * * 回溯法
    * 1. 依次从nums中取出一个元素，加入到tmp数组尾部；
    * 2. 将取出元素的下标保存在visited 集合中，用于标记已取出的元素；
    * 3. 取出一个后，递归取出其他未取出的元素；
    * 4. 当tmp的个数满了后，递归函数返回，将tmp加入到结果列表中；
    * 5. 递归函数返回时，需将之前所取元素放回，再处理下一个元素；
    */
    vector<vector<int>> permute(vector<int>& nums) {
        vector<int> tmp;            //一次排列
        set<int> visited;           //记录已取元素下标
        dfs(nums, tmp, visited);

        return result;
    }

    void dfs(vector<int>&nums, vector<int>& tmp, set<int>& visited) {
        if (tmp.size() == nums.size()) {
            result.push_back(tmp);
            return;
        }
        for(int j=0; j<nums.size(); j++) {
            //跳过已取出的元素
            if (visited.find(j)!=visited.end()) {
                continue;
            }

            //将未取出的元素取出，加入到tmp中
            tmp.push_back(nums[j]);
            visited.insert(j);  //并记录到visited 集合中；
            //递归处理其他元素
            dfs(nums, tmp, visited);
            //递归返回时，放回已取出的元素
            tmp.pop_back();
            visited.erase(j);
        }
    }
};

 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

struct Solution;

// @lc code=start
impl Solution {
    /// ## 解题思路
    /// - 回溯法
    pub fn permute(nums: Vec<i32>) -> Vec<Vec<i32>> {
        let mut res: Vec<Vec<i32>> = vec![];

        /// 回溯
        fn _permute(nums: &[i32], tmp: &[i32], res: &mut Vec<Vec<i32>>) {
            // 终止条件
            if nums.is_empty() {
                res.push(tmp.to_vec());
                return;
            }

            // 遍历
            for (i, &val) in nums.iter().enumerate() {
                let (mut nums_v, mut tmp_v) = (nums.to_vec(), tmp.to_vec());
                nums_v.remove(i);
                tmp_v.push(val);
                // 
                _permute(&nums_v, &tmp_v, res);
            }
        }

        _permute(&nums, &vec![], &mut res);

        res
    }
}
// @lc code=end