LeetCode第46题全排列

继续打卡算法题，今天学习的是LeetCode第46题全排列，这道题目是道中等题。算法题的一些解题思路和技巧真的非常巧妙，每天看一看算法题和解题思路，我相信对我们的编码思维和编码能力有一些提升。

分析一波题目

哈哈，学习过之前的组合问题，这道题目就简单了，解决方法一样使用回溯来解决。

组合和排列定义不一样，组合的元素是无序的，而排列组成的元素是有序的,比如数组[1,2]的全组合只有[1,2],但是排列有[1,2]和[2,1]。

所以排列和组合取数有点区别，每次取其他元素需从第一个开始取，并且已经取过的不能取了，所以我们需要记录当前排列哪些数据已经取过了。

本题解题技巧

1、理解排列定义，排列是有顺序的。

2、每次都从第一个元素开始取数，但是一个数字在一个排列中只能出现一次。

编码解决

下面代码和组合总和II的代码非常相似。

class Solution {
    public List<List<Integer>> permute(int[] nums) {

        //递归 回溯
        boolean[] used = new boolean[nums.length];
        backtracking(nums, new ArrayList<>(), 0, 0, used);
        return result;
    }

    private List<List<Integer>> result = new ArrayList<>();


    public void backtracking(int[] nums,List<Integer> path, int startIndex, int sum, boolean[] used) {

        //结束条件
        if(path.size() == nums.length) {
            result.add(new ArrayList(path));
            return;
        }
 
        //递归单层逻辑
        for(int i=startIndex; i<nums.length; i++) {
               if(used[i] == true) {
                   continue;
               }
               path.add(nums[i]);
               sum += nums[i];
               used[i] = true;
               //开始递归 startIndex传i,就是考虑每个数字都可以重复使用的情况
               backtracking(nums, path, 0, sum, used);
               //回溯
               sum = sum - nums[i];
               used[i] = false;
               path.remove(path.size()-1);
        }
    }

}

总结

排列和组合都可以通过回溯法解决，理解了回溯解法之后，解决这种问题比较简单，这两类题目建议画出树图可以更好的理解递归逻辑。