DFS-Recall3

发表于 分类于 ，

原题描述[原题链接][https://leetcode-cn.com/problems/permutations/]

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

示例:

输入: [1,2,3]
输出:
[
[1,2,3],
[1,3,2],
[2,1,3],
[2,3,1],
[3,1,2],
[3,2,1]
]

算法描述

​ 题目给出了没有重复数字，设置一个标记即可，记录该元素是否使用过，还需要一个递归出口，当排列数长度等于给出的序列时，将结果添加到结果中，结束后需要回溯操作，将之前的标记清除，让这个元素变成可用；

C++代码

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
class Solution {
public:
    int n;
    vector<bool> flag;
    vector<vector<int>> ans;
    vector<int> path;
    vector<vector<int>> permute(vector<int>& nums) {
        n = nums.size();
        flag = vector<bool>(n);
        
        dfs(nums,0);
        
        return ans;
    }
    
    void dfs(vector<int>& nums,int u){
        if(u==n){
            ans.push_back(path);
            return ;
        }
        for(int i=0;i<nums.size();i++){
            if(!flag[i]){
                flag[i] = true;
                path.push_back(nums[i]);
                dfs(nums,u+1);
                path.pop_back();
                flag[i] = false;
            }
        }
    }
};

Java代码

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
class Solution {
    int n;
    int[] flag;
    List<List<Integer>> ans;
    List<Integer> path;
    public List<List<Integer>> permute(int[] nums) {
        n = nums.length;
        flag = new int[n];
        path = new ArrayList<Integer>();
        ans = new ArrayList<List<Integer>>();
        dfs(nums,0);
        
        return ans;
    }
    
    public void dfs(int[] nums,int u){
        if(u==n){
            ans.add(new ArrayList<>(path));
            return ;
        }
        for(int i=0;i<n;i++){
            if(flag[i]==0){
                flag[i]=1;
                path.add(Integer.valueOf(nums[i]));
                dfs(nums,u+1);
                path.remove(Integer.valueOf(nums[i]));
                flag[i]=0;
            }
        }
    }
}