题目: 全排列

全排列可以使用暴力破解，因为数组里面的数字是不重复的，所以以此将这些数字放在不同的位置就构成了一次排列，暴力破解是遍历所有的排列。

回溯法是实现暴力破解的一种方式。

回溯法

回溯法解决全排列问题示意图

回溯法流程的通用模版可以抽象如下：

backtrack{

如果到达终止条件：

将该路径加入结果列表；

循环选择列表:

  #将该选择添加到选择路径

  路径.add(选择)

  backtrack(路径, 选择列表)

  # 撤销选择

  路径.remove(选择）

}

在本题中，回溯法可以选择的值是集合中的元素，但是本次选择不可以选择已经在路径中存在的元素。

回溯法结束的条件是路径上的元素个数已经等于集合中的元素个数。

字典序

字典序是按照字符排序的一种排列方式。字典序算法具体的实现方案如下：

从右到左，找出第一个非递增的数字，假如位置为i;

从右向左，找出第一个大于a[i]的元素以及位置，假如该位置为j;

交换A[i]与A[j]两个元素；

从i位置对后面所有元素进行逆序排列；

题解

回溯法

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

public class Solution {

    List<List<Integer>> result = new LinkedList<>();
    LinkedList<Integer> backTrackPath = new LinkedList<>();


    public List<List<Integer>> solute(int[] nums) {
        boolean[] numUsedState = new boolean[nums.length];
        backTracking(nums, numUsedState);
        return result;
    }

    public void backTracking(int[] nums, boolean[] numUsedState) {
        if (backTrackPath.size() == nums.length) {
            result.add(new ArrayList<>(backTrackPath));
            return;
        }

        for (int i = 0; i < nums.length; i++) {
            if (numUsedState[i]) {
                continue;
            }
            backTrackPath.add(nums[i]);
            numUsedState[i] = true;

            backTracking(nums, numUsedState);

            numUsedState[i] = false;
            backTrackPath.removeLast();
        }
    }
}