剑指 Offer II 083. 没有重复元素集合的全排列

解题思路

解法：
1.审题可知，其实就是回溯算法的应用
2.排列组合的回溯算法实现

回溯算法理解

概念

回溯算法实际上一个类似枚举的搜索尝试过程，主要是在搜索尝试过程中寻找问题的解，当发现已不满足求解条件时，就“回溯”返回，尝试别的路径。回溯法是一种选优搜索法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。许多复杂的，规模较大的问题都可以使用回溯法，有“通用解题方法”的美称。

回溯其实也是一种递归，有以下四个参数，当然不一定是我所举例的类型，要看题目而定一个全局变量集合保存所有满足条件的答案，举例：List<List<Integer>> list，一个集合保存一个满足条件的答案，举例：List<Integer> tempList，算法问题给所给的输入条件，这个可能是一个字符串，也可能是一个数组

总结

此题解法的理解，其实就是for循环，从0开始，递归遍历，以1开头的所有情况，遍历过程中，需要判断当前解中是否含有当前元素了，如果含有，则继续。然后判断以2开头的所有情况。直到数组末尾元素为头的情况遍历完成。

##解法1
import java.util.ArrayList;
import java.util.List;

class Solution {
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> ans = new ArrayList<List<Integer>>();
        List<Integer> temp = new ArrayList<>();
        backSearch(ans, temp, nums);
        return ans;
    }

    private void backSearch(List<List<Integer>> ans, List<Integer> temp,
            int[] nums) {
        if (temp.size() == nums.length) {
            //需要new arraylist添加，不然添加的是同一个对象，而且temp对象数据，最终肯定是空
            ans.add(new ArrayList<>(temp));
        } else {
            for (int i = 0; i < nums.length; i++) {
                if (!temp.contains(nums[i])) {
                    temp.add(nums[i]);
                    backSearch(ans, temp, nums);
                    temp.remove(temp.size() - 1);
                }
            }
        }
    }
}