LeetCode46- Full Permutation

One 、 Title Description

Two 、 Backtracking tree

There are generally two ways to write the backtracking tree of common arrangement problems , The corresponding diagram is given below ：

2.1 be based on swap Backtracking tree

The depth of the tree deepens every layer , Then the branches of each node in this layer will be reduced 1, For example 0 Layer is 3 Branches , In the first 1 layer , Each node has only two branches

2.2 be based on visited Backtracking tree of array

Each layer is still expanded by three nodes , But repeated knots will be pruned , This will also get the backtracking tree of the permutation problem

3、 ... and 、 Code implementation

3.1 be based on swap Backtracking tree code

class Solution {
    
    public List<List<Integer>> permute(int[] nums) {
    
        List<List<Integer>> res = new ArrayList<>();
        solve(nums, 0, res);
        return res;
    }

    public void solve(int[] nums, int startIndex, List<List<Integer>> res) {
    
        if (startIndex >= nums.length) {
    
            List<Integer> curRes = new ArrayList<>();
            for (int i = 0; i < nums.length; i++) {
    
                curRes.add(nums[i]);
            }
            res.add(curRes);
            return;
        }

        for (int i = startIndex; i < nums.length; i++) {
    
            swap(nums, i, startIndex);
            solve(nums, startIndex + 1, res);
            swap(nums, i, startIndex);
        }
    }

    private void swap(int[] nums, int i, int j) {
    
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }
}

3.2 be based on visited Array backtracking tree code

class Solution {
    
    public List<List<Integer>> permute(int[] nums) {
    
        List<List<Integer>> res = new ArrayList<>();
        boolean[] visited = new boolean[nums.length];
        solve(nums, 0, res, new ArrayList<>(), visited);
        return res;
    }

    public void solve(int[] nums, int startIndex, List<List<Integer>> res, List<Integer> curRes, boolean[] visited) {
    
        if (startIndex == nums.length) {
    
            res.add(new ArrayList<>(curRes));
            return;
        }

        for (int i = 0; i < nums.length; i++) {
    
            if (visited[i]) {
    
                continue;
            }
            curRes.add(nums[i]);
            visited[i] = true;
            solve(nums, startIndex + 1, res, curRes, visited);
            curRes.remove(curRes.size() - 1);
            visited[i] = false;
        }
    }
}