【Hot100】LeetCode—46. 全排列

• 题目连接：46. 全排列

1- 思路

回溯

• 由于是排列问题，需要讲究元素顺序。元素相同顺序不同是不同的排列，而组合问题不强调元素顺序。
• 组合中的 startIndex 是用来保证，不会出现 [1,2] [2,1] 的情况，因此本题是排列，需要 [1,2] [2,1] 的情况，所以是有必要的。

回溯三部曲

• 1. 终止条件
  • 结果长度为 数组长度的时候，收集结果到 res 中
• 2. 回溯逻辑，需要用 used 数组去重

2- 实现

⭐46. 全排列——题解思路

class Solution {

    List<List<Integer>> res = new ArrayList<>();
    List<Integer> path = new ArrayList<>();
    boolean[] used;
    public List<List<Integer>> permute(int[] nums) {
        used = new boolean[nums.length];
        Arrays.fill(used,false);
        backTracing(nums);
        return res;
    }

    public  void backTracing(int[] nums){
        // 终止条件
        if(path.size() == nums.length){
            res.add(new ArrayList(path));
            return ;
        }

        // 遍历
        // 树宽 
        for(int i = 0;i<nums.length;i++){
            if(used[i]){
                continue;
            }
            used[i] = true;
            path.add(nums[i]);
            backTracing(nums);
            path.remove(path.size()-1);
            used[i] = false;
        }
    }
}

3- ACM 实现

public class permute {

    List<List<Integer>> res = new ArrayList<>();
    List<Integer> path = new ArrayList<>();
    boolean[] used;
    public List<List<Integer>> permute(int[] nums) {
        used = new boolean[nums.length];
        Arrays.fill(used,false);
        backTracing(nums);
        return res;
    }

    public  void backTracing(int[] nums){
        // 终止条件
        if(path.size() == nums.length){
            res.add(new ArrayList(path));
            return ;
        }

        // 遍历
        // 树宽
        for(int i = 0;i<nums.length;i++){
            if(used[i]){
                continue;
            }
            used[i] = true;
            path.add(nums[i]);
            backTracing(nums);
            path.remove(path.size()-1);
            used[i] = false;
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String input = sc.nextLine();
        input = input.replace("[","").replace("]","");
        String[] parts = input.split(",");
        int[] nums = new int[parts.length];
        for(int i = 0 ; i < nums.length;i++){
            nums[i] = Integer.parseInt(parts[i]);
        }
        permute p = new permute();

        List<List<Integer>> result = p.permute(nums);
        System.out.println("结果是"+result.toString());
    }
}