全排列

import java.util.Arrays;

public class Permutations {
	public static void dfs(int[] arr, int start, int end) {
		if (start == end) {
			System.out.println(Arrays.toString(arr));
		} else {
			for (int i = start; i <= end; i++) {
                // 交换元素
				swap(arr, start, i);
                // 递归求解
				dfs(arr, start + 1, end);
                // 回溯，恢复原来的顺序
				swap(arr, start, i);
			}
		}
	}

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

	public static void main(String[] args) {
		int[] arr = { 1, 2, 3 };
		int n = arr.length;
		System.out.println("All permutations of the array:");
		dfs(arr, 0, n - 1);
	}
}

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

public class Permutations2 {
	// 存放符合条件结果的集合
	static List<List<Integer>> result = new ArrayList<>();
	// 存放符合条件结果
	static LinkedList<Integer> path = new LinkedList<>();
	// 记录数组元素的访问情况
	static boolean[] used;

	static List<List<Integer>> permute(int[] nums) {
		if (nums.length == 0) {
			return result;
		}
		used = new boolean[nums.length];
		backtrack(nums);
		return result;
	}

	static void backtrack(int[] nums) {
		if (path.size() == nums.length) {
			result.add(new ArrayList<>(path));
			return;
		}
		for (int i = 0; i < nums.length; i++) {
			if (!used[i]) {
				used[i] = true;
				path.add(nums[i]);
				backtrack(nums);
				path.removeLast();
				used[i] = false;
			}
		}
	}

	public static void main(String[] args) {
		int[] nums = { 1, 2, 3 };
		List<List<Integer>> permutations = permute(nums);
		System.out.println("All permutations:");
		for (List<Integer> permutation : permutations) {
			System.out.println(permutation);
		}
	}
}