最近写了一些关于回溯算法的题目,相比刚接触算法时来说,对回溯的理解有了更深的认识。这道题是我认为比较经典的题目,能体现回溯算法的一般特性。

问题:给定一个可包含重复数字的序列,返回所有不重复的全排列。

示例:

1
2
3
4
5
6
7
输入: [1,1,2]
输出:
[
  [1,1,2],
  [1,2,1],
  [2,1,1]
]

回溯问题的一般思路:

  1. 先查明是否是回溯可解问题。
  2. 分析回溯树的类型和进入节点前后所需做的操作。
  3. 确定遍历是否是顺序遍历,如果是顺序遍历的话,则无需额外的boolean[] visited数组。
  4. 确定回溯入口和出口。
  5. 根据问题本身特点及回溯树特点来确定剪枝方法。
  6. 编写回溯函数。

以这道题为例:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
class Solution {
    public List<List<Integer>> permuteUnique(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        if(nums == null || nums.length == 0){
            return result;
        }
        //回溯入口处的处理
        Arrays.sort(nums);//排序便于剪枝
        boolean[] visited = new boolean[nums.length];//boolean数组用于遍历
        //回溯
        backtrack(nums, visited, result, new LinkedList<Integer>());
        return result;
    }
	//回溯函数
    public void backtrack(int[] nums, boolean[] visited, List<List<Integer>> result, LinkedList<Integer> tempList){
        
        if(tempList.size() == nums.length){
            result.add(new LinkedList(tempList));
            return;
        }
        for(int i = 0; i < nums.length; i++){
            //剪枝函数,首先为了剪枝已经在回溯前对数组进行了排序。之后对于任意一个节点,如果是第二次访问的话,如果和之前访问过的数值相同的节点不在同一层,则可以继续回溯,反之则会重复。即通过i > 0 && nums[i] == nums[i - 1] && !visited[i - 1]实现上述分析。
            if(visited[i] || i > 0 && nums[i] == nums[i - 1] && !visited[i - 1]){
                continue;
            }
            //进入节点前的操作
            visited[i] = true;
            tempList.add(nums[i]);
            //回溯
            backtrack(nums, visited, result, tempList);
            //退出节点时的操作
            tempList.removeLast();
            visited[i] = false;
        }
    }
}

个人认为回溯问题最难的部分在于剪枝函数的选取,一般是需要画出回溯树来进行具体问题具体分析的,很难说有什么所谓套路可言,挺有意思的。对于这个题而言,剪枝函数的选取和编写技巧性很强,且对于结果不能重复的问题而言比较通用,思路一通百通。

这里贴一个分析比较好的题解链接:https://leetcode-cn.com/problems/permutations-ii/solution/hui-su-suan-fa-python-dai-ma-java-dai-ma-by-liwe-2/