什么是回溯算法

本篇内容介绍了"什么是回溯算法"的有关知识，在实际案例的操作过程中，不少人都会遇到这样的困境，接下来就让小编带领大家学习一下如何处理这些情况吧！希望大家仔细阅读，能够学有所成！

Example 1:

Input: nums = [1,1,2]Output:[[1,1,2],[1,2,1],[2,1,1]]

Example 2:

Input: nums = [1,2,3]Output: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

Constraints:

• 1 <= nums.length <= 8

• -10 <= nums[i] <= 10

Analysis

回溯算法

与LeetCode - Medium - 46. Permutations类似，不同之处在于给定一个可包含重复数字的序列，要返回所有不重复的全排列，这里涉及到去重。

去重一定要对元素进行排序，这样我们才方便通过相邻的节点来判断是否重复使用。

以示例中的 [1,1,2]为例 （为了方便举例，已经排序）抽象为一棵树，去重过程如图：

图中我们对同一树层，前一位（也就是nums[i-1]）如果使用过，那么就进行去重。

拓展

去重最为关键的代码为：

if (used[i] || i > 0 && nums[i - 1] == nums[i] && !used[i - 1])        continue;

如果将!used[i - 1]改成 used[i - 1]， 结果也是正确的！很神奇。

if (used[i] || i > 0 && nums[i - 1] == nums[i] && used[i - 1])        continue;

这是为什么呢，就是上面我刚说的，如果要对树层中前一位去重，就用!used[i - 1]。如果要对树枝前一位去重用used[i - 1]。

对于排列问题，树层上去重和树枝上去重，都是可以的，但是树层上去重效率更高！

用[1,1] 来举一个例子。

树层上去重(!used[i - 1])，的树形结构如下：

树枝上去重（used[i - 1]）的树型结构如下：

用[1,1,1] 再来举一个例子。

树层上去重(!used[i - 1])，的树形结构如下：

树枝上去重（used[i - 1]）的树型结构如下： 显然，树层上对前一位去重非常彻底，效率很高，树枝上对前一位去重虽然最后可以得到答案，但是做了很多无用搜索。

小结

树层上去重要加上!used[i - 1]，似非而是，代码结合图加深理解吧！

参考

1. 回溯算法：排列问题（二）

Submission

import java.util.ArrayList;import java.util.Arrays;import java.util.List;public class PermutationsII {        public List> permuteUnique(int[] nums) {                List> result = new ArrayList<>();                List path = new ArrayList<>();                boolean[] used = new boolean[nums.length];                Arrays.sort(nums);                backtracking(path, nums, used, result);                return result;        }        private void backtracking(List path, int[] nums, boolean[] used, List> result) {                if (path.size() == nums.length) {                        result.add(new ArrayList<>(path));                        return;                }                for (int i = 0; i < nums.length; i++) {                        if (used[i] || i > 0 && nums[i - 1] == nums[i] && !used[i - 1])                                continue;                        used[i] = true;                        path.add(nums[i]);                        backtracking(path, nums, used, result);                        path.remove(path.size() - 1);                        used[i] = false;                }        }}

Test

import static org.junit.Assert.*;import java.util.ArrayList;import java.util.Arrays;import java.util.List;import static org.hamcrest.collection.IsIterableContainingInAnyOrder.containsInAnyOrder;import org.hamcrest.Matcher;import org.junit.Test;@SuppressWarnings("unchecked")public class PermutationsIITest {        private final int[] array1 = {1, 1, 2};        private final int[] array2 = {1, 2, 3};        private final int[] array3 = {0, 1, 0, 0, 9};                private final Matcher>> expected1 = containsInAnyOrder(Arrays.asList(1,1,2), //                         Arrays.asList(1,2,1), Arrays.asList(2,1,1));        private final Matcher>> expected2 = containsInAnyOrder(Arrays.asList(1,2,3), Arrays.asList(1,3,2),//                         Arrays.asList(2,1,3), Arrays.asList(2,3,1), Arrays.asList(3,1,2), Arrays.asList(3, 2, 1));                private final String expected3String = "[0,0,0,1,9],[0,0,0,9,1],[0,0,1,0,9],[0,0,1,9,0],[0,0,9,0,1],"//                                                                        + "[0,0,9,1,0],[0,1,0,0,9],[0,1,0,9,0],[0,1,9,0,0],[0,9,0,0,1],"//                                                                        + "[0,9,0,1,0],[0,9,1,0,0],[1,0,0,0,9],[1,0,0,9,0],[1,0,9,0,0],"//                                                                        + "[1,9,0,0,0],[9,0,0,0,1],[9,0,0,1,0],[9,0,1,0,0],[9,1,0,0,0]";                        private final Matcher>> expected3 = containsInAnyOrder(string2IntegerList(expected3String));                @Test        public void test() {                PermutationsII obj = new PermutationsII();                assertThat(obj.permuteUnique(array1), expected1);                assertThat(obj.permuteUnique(array2), expected2);                assertThat(obj.permuteUnique(array3), expected3);        }                private List[] string2IntegerList(String original){                List[] result;                original = original.substring(1, original.length() - 1);                String[] strs = original.split("\\],\\[");                result = new ArrayList[strs.length];                for(int i = 0; i < strs.length; i++) {                        String[] nums = strs[i].split(",");                        List list = new ArrayList<>();                        for(String num : nums) {                                list.add(Integer.valueOf(num));                        }                        result[i] = list;                }                return result;        }                        @Test        public void testString2IntegerList() {                String str = "[0,0,0,1,9],[0,0,0,9,1],[0,0,1,0,9],[0,0,1,9,0],[0,0,9,1,0],"                                + "[0,0,9,0,1],[0,1,0,0,9],[0,1,0,9,0],[0,1,9,0,0],[0,9,0,1,0],"                                + "[0,9,0,0,1],[0,9,1,0,0],[0,9,0,1,0],[0,9,0,0,1],[1,0,0,0,9],"                                + "[1,0,0,9,0],[1,0,9,0,0],[1,9,0,0,0],[9,0,0,1,0],[9,0,0,0,1],"                                + "[9,0,1,0,0],[9,0,0,1,0],[9,0,0,0,1],[9,1,0,0,0],[9,0,0,1,0],"                                + "[9,0,0,0,1],[9,0,1,0,0],[9,0,0,1,0],[9,0,0,0,1]";                System.out.println(string2IntegerList(str));        }        }

"什么是回溯算法"的内容就介绍到这里了，感谢大家的阅读。如果想了解更多行业相关的知识可以关注网站，小编将为大家输出更多高质量的实用文章！