回溯算法 | 青柠

回溯算法模板伪代码

回溯算法本质上还是DFS算法

LinkedList<Integer> trace = new LinkedList<>();

private void backtrack(int[] candidates) {

    for (int i = 0; i < candidates.length; i++) {
        
        // 前进
        trace.addLast(candidates[i]);
        backtrack(candidates);
        // 回退
        trace.removeLast();
    }
}

回溯算法解决的问题

回溯算法主要用于解决子集、组合和排列问题，通过对所经过的节点路径进行追踪

子集问题

子集问题只能不可重复使用

元素不重复

假设存在数组candidates = [2, 6 ,7]，对应子集如下：

[[], [2], [6], [7], [2,6], [2,7], [6,7], [2,6,7]]

通过树构建如下：

每个子树中，根节点的子节点都是数组当前元素后面的元素，比如节点2，子节点就是[6, 7]，节点6，子节点就是[7]，也就是说每次遍历子节点都是从数组中当前节点位置的后一个索引位置开始，伪代码如下：

LinkedList<Integer> trace = new LinkedList<>();

private void backtrack(int[] candidates, int start) {

    for (int i = start; i < candidates.length; i++) {
        
        // 前进
        trace.addLast(candidates[i]);
        // 比如当前在节点2位置，也就是i=0，那么遍历节点2的子节点时就要从索引1位置开始
        backtrack(candidates, i+1);
        // 回退
        trace.removeLast();
    }
}

元素重复

如果元素可重复选，那么子集又是怎样的呢？

假设存在数组candidates = [2, 2 ,6]，其中元素2存在相同，对应子集如下：

[[], [2], [6], [2,2], [2,6], [2,2,6]]

通过树构建如下：

其中子集[2]与[2]重复，[2,6]与[2,6]重复

现在问题是：如何才能去除重复子集呢？

其实看图你会发现，以每个节点作为整个树的子树的根节点，相同元素节点一定是左边子树的子集包含右边同元素节点的子集；

比如左边子树2与右边子树2是相同的元素，其左边子树的子集[[2], [2,2], [2,6]]包含了右边子树所有的子集[[2],[2,6]；

既然知道了规律，那么怎么去除呢？

解决方法：只要在处理重复节点的时候直接跳过即可

基于上面的伪代码进行改造，如下：

LinkedList<Integer> trace = new LinkedList<>();

private void do(int[] candidates, int start) {
	
    // 对数据进行排序，方便重复处理时跳过相同元素
    Arrays.sort(candidates);
    backtrack(candidates, start);
}

private void backtrack(int[] candidates, int start) {

    for (int i = start; i < candidates.length; i++) {
        
        // 如果当前节点元素值等于左边节点元素值，那么直接跳过 
        if(i > start && candidates[i] == candidates[i-1]){
            // do something
            continue;
        }
        // 前进
        trace.addLast(candidates[i]);
        // 比如当前在节点2位置，也就是i=0，那么遍历节点2的子节点时就要从索引1位置开始
        backtrack(candidates, i+1);
        // 回退
        trace.removeLast();
    }
}