实现元素全排列

嗯……继我的启蒙算法实现求集合的子集后，又总结一种类似的常用的算法（我觉得，不接受反驳）。

同样的，有递归和非递归两种方法

代码如下：

import java.util.ArrayList;
import java.util.List;

public class ArraysArrange {
    public static void main(String[] args) {
        int[] nums = {1, 2, 3};
        List<List<Integer>> result = new ArrayList<>();
        permute(nums, 0, result);
        for (List<Integer> list : result) {
            System.out.println(list);
        }
    }

    public static void permute(int[] nums, int start, List<List<Integer>> result) {
        // 基本情况：如果start等于nums的长度，说明已经得到一个排列
        if (start == nums.length - 1) {
            List<Integer> permutation = new ArrayList<>();
            for (int num : nums) {
                permutation.add(num);
            }
            result.add(permutation);
            return;
        }

        // 递归步骤：遍历数组，交换元素并递归
        for (int i = start; i < nums.length; i++) {
            // 交换元素
            swap(nums, i, start);
            // 递归调用，进入下一层
            permute(nums, start + 1, result);
            // 回溯：将元素换回原来的位置
            swap(nums, start, i);
        }
    }

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

非递归方式

import java.util.*;

public class ArraysArrange2 {
    public static void main(String[] args) {
        int[] nums = {1, 2, 3};
        List<List<Integer>> result = new ArrayList<>();
        backtrack(result, new ArrayList<>(), nums);
        for (List<Integer> list : result) {
            System.out.println(list);
        }
    }

    private static void backtrack(List<List<Integer>> result, List<Integer> current, int[] nums) {
        if (current.size() == nums.length) {
            result.add(new ArrayList<>(current));
            return;
        }

        for (int i = 0; i < nums.length; i++) {
            // 检查是否已经添加过nums[i]到current
            if (current.contains(nums[i])) continue;

            current.add(nums[i]);
            backtrack(result, current, nums);
            current.remove(current.size() - 1); // 回溯
        }
    }
}