全排列一篇看懂回溯解法题目给定一个不含重复数字的整数数组nums返回它的所有全排列。示例输入nums[1,2,3]输出[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]一、题目这道题的核心是把数组中的每个数字都轮流放到当前位置上直到所有位置都放满。比如nums [1,2,3]第一位可以放1第一位也可以放2第一位还可以放3每确定一位就继续递归处理下一位。这就是典型的回溯问题。二、最容易想到的思路可以这样理解先确定第0个位置放谁再确定第1个位置放谁再确定第2个位置放谁当所有位置都确定后就得到一个排列为了高效我们通常使用交换的方式而不是每次都新建数组。三、回溯解法代码importjava.util.ArrayList;importjava.util.List;classSolution{publicListListIntegerpermute(int[]nums){ListListIntegerresnewArrayList();backtrack(nums,0,res);returnres;}privatevoidbacktrack(int[]nums,intfirst,ListListIntegerres){if(firstnums.length){ListIntegerlistnewArrayList();for(intnum:nums){list.add(num);}res.add(list);return;}for(intifirst;inums.length;i){swap(nums,first,i);// 选择一个数放到当前位置backtrack(nums,first1,res);// 递归处理下一个位置swap(nums,first,i);// 恢复现场}}privatevoidswap(int[]nums,inti,intj){inttempnums[i];nums[i]nums[j];nums[j]temp;}}四、为什么这样做可行假设数组是[1,2,3]第一步确定第 0 位把1放到第 0 位数组还是[1,2,3]把2放到第 0 位数组变成[2,1,3]把3放到第 0 位数组变成[3,2,1]第二步递归确定后面的位例如已经确定第 0 位是1那后面就去处理[2,3]的排列。最后会得到[1,2,3][1,3,2]再继续处理第 0 位是2、第 0 位是3的情况。五、为什么交换后还要交换回来这是回溯最关键的一步。例如当前数组是[1,2,3]当我们尝试把2放到第 0 位时会执行swap(nums,0,1)数组变成[2,1,3]递归处理完以后如果不换回来数组就一直是[2,1,3]会影响后面继续尝试别的情况。所以必须再交换一次swap(nums,0,1)把数组恢复成原来的样子[1,2,3]这样下一轮尝试才不会出错。一句话概括交换过去是做选择交换回来是撤销选择。六、执行过程示例以nums [1,2,3]为例第一层确定第 0 位选1得到[1,2,3]选2得到[2,1,3]选3得到[3,2,1]第二层确定第 1 位例如当前是[1,2,3]选2得到[1,2,3]选3得到[1,3,2]第三层确定第 2 位只剩最后一个数直接加入结果。最终得到全部 6 种排列。七、复杂度分析时间复杂度O(n × n!)原因一共有n!种排列每次加入答案时需要把当前数组复制到结果中花费O(n)空间复杂度O(n)主要是递归调用栈的深度。不计最终答案所占空间。八、这道题的本质这道题的本质不是“交换”而是枚举每个位置可以放哪些数。交换只是一个实现手段它的优点是不需要额外创建很多新数组代码更简洁性能更好九、总结这道题是经典的回溯题。可以记住下面这个模板做选择 递归 撤销选择对应到本题就是swap(nums,first,i);backtrack(nums,first1,res);swap(nums,first,i);其中swap把一个数放到当前的位置backtrack递归处理下一个位置再swap恢复现场继续尝试别的数十、结论全排列问题最经典的解法就是回溯 交换。它的核心思想是每一层确定一个位置放什么通过交换把候选数字放到当前位置递归处理剩余位置处理完再恢复原数组
LeetCode-44 回溯解法
全排列一篇看懂回溯解法题目给定一个不含重复数字的整数数组nums返回它的所有全排列。示例输入nums[1,2,3]输出[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]一、题目这道题的核心是把数组中的每个数字都轮流放到当前位置上直到所有位置都放满。比如nums [1,2,3]第一位可以放1第一位也可以放2第一位还可以放3每确定一位就继续递归处理下一位。这就是典型的回溯问题。二、最容易想到的思路可以这样理解先确定第0个位置放谁再确定第1个位置放谁再确定第2个位置放谁当所有位置都确定后就得到一个排列为了高效我们通常使用交换的方式而不是每次都新建数组。三、回溯解法代码importjava.util.ArrayList;importjava.util.List;classSolution{publicListListIntegerpermute(int[]nums){ListListIntegerresnewArrayList();backtrack(nums,0,res);returnres;}privatevoidbacktrack(int[]nums,intfirst,ListListIntegerres){if(firstnums.length){ListIntegerlistnewArrayList();for(intnum:nums){list.add(num);}res.add(list);return;}for(intifirst;inums.length;i){swap(nums,first,i);// 选择一个数放到当前位置backtrack(nums,first1,res);// 递归处理下一个位置swap(nums,first,i);// 恢复现场}}privatevoidswap(int[]nums,inti,intj){inttempnums[i];nums[i]nums[j];nums[j]temp;}}四、为什么这样做可行假设数组是[1,2,3]第一步确定第 0 位把1放到第 0 位数组还是[1,2,3]把2放到第 0 位数组变成[2,1,3]把3放到第 0 位数组变成[3,2,1]第二步递归确定后面的位例如已经确定第 0 位是1那后面就去处理[2,3]的排列。最后会得到[1,2,3][1,3,2]再继续处理第 0 位是2、第 0 位是3的情况。五、为什么交换后还要交换回来这是回溯最关键的一步。例如当前数组是[1,2,3]当我们尝试把2放到第 0 位时会执行swap(nums,0,1)数组变成[2,1,3]递归处理完以后如果不换回来数组就一直是[2,1,3]会影响后面继续尝试别的情况。所以必须再交换一次swap(nums,0,1)把数组恢复成原来的样子[1,2,3]这样下一轮尝试才不会出错。一句话概括交换过去是做选择交换回来是撤销选择。六、执行过程示例以nums [1,2,3]为例第一层确定第 0 位选1得到[1,2,3]选2得到[2,1,3]选3得到[3,2,1]第二层确定第 1 位例如当前是[1,2,3]选2得到[1,2,3]选3得到[1,3,2]第三层确定第 2 位只剩最后一个数直接加入结果。最终得到全部 6 种排列。七、复杂度分析时间复杂度O(n × n!)原因一共有n!种排列每次加入答案时需要把当前数组复制到结果中花费O(n)空间复杂度O(n)主要是递归调用栈的深度。不计最终答案所占空间。八、这道题的本质这道题的本质不是“交换”而是枚举每个位置可以放哪些数。交换只是一个实现手段它的优点是不需要额外创建很多新数组代码更简洁性能更好九、总结这道题是经典的回溯题。可以记住下面这个模板做选择 递归 撤销选择对应到本题就是swap(nums,first,i);backtrack(nums,first1,res);swap(nums,first,i);其中swap把一个数放到当前的位置backtrack递归处理下一个位置再swap恢复现场继续尝试别的数十、结论全排列问题最经典的解法就是回溯 交换。它的核心思想是每一层确定一个位置放什么通过交换把候选数字放到当前位置递归处理剩余位置处理完再恢复原数组
