回溯总结

模板

选自labuladong的文章

框架：

result = []
def backtrack(路径, 选择列表):
    if 满足结束条件:
        result.add(路径)
        return

    for 选择 in 选择列表:
        做选择
        backtrack(路径, 选择列表)
        撤销选择

模板代码： 解决全排列问题

List<List<Integer>> res = new LinkedList<>();

/* 主函数，输入一组不重复的数字，返回它们的全排列 */
List<List<Integer>> permute(int[] nums) {
    // 记录「路径」
    LinkedList<Integer> track = new LinkedList<>();
    backtrack(nums, track);
    return res;
}

// 路径：记录在 track 中
// 选择列表：nums 中不存在于 track 的那些元素
// 结束条件：nums 中的元素全都在 track 中出现
void backtrack(int[] nums, LinkedList<Integer> track) {
    // 触发结束条件
    if (track.size() == nums.length) {
        res.add(new LinkedList(track));
        return;
    }

    for (int i = 0; i < nums.length; i++) {
        // 排除不合法的选择
        if (track.contains(nums[i]))
            continue;
        // 做选择
        track.add(nums[i]);
        // 进入下一层决策树
        backtrack(nums, track);
        // 取消选择
        track.removeLast();
    }
}

改进

1.利用visited[]数组来去重选择
2.设置k来对结果进行长度排序

1.利用visited[]数组来去重选择

利用visited[]数组来使得nums数组（输入数组）中的元素只能被选择一次，visited[i]为true的时候说明该元素已被选择直接跳过，否则选取该元素
字符串的排列

代码如下：

import java.util.ArrayList;
import java.util.Arrays;
public class Solution {
    ArrayList<String> res = new ArrayList<String>();
    boolean[] visited;
    public ArrayList<String> Permutation(String str) {
        char[] ch = str.toCharArray();
        visited = new boolean[str.length()];
        StringBuilder sb = new StringBuilder();
        backtrack(ch, sb);
        return res;
    }
    public void backtrack (char[] ch, StringBuilder sb) {
        if (sb.length() == ch.length) {
            String s = new StringBuilder(sb).toString();
            if (!res.contains(s))
                res.add(s);
            return;
        }
        for (int i = 0; i < ch.length; i++) {
            if (visited[i])
                continue;
            visited[i] = true;
            sb.append(ch[i]);
            backtrack(ch, sb);
            visited[i] = false;
            sb.deleteCharAt(sb.length()-1);
        }
    }
}

2.设置k来对结果进行长度排序

输入：[1,2,3]
正常全排列输出：[[],[1],[1,2],[1,2,3],[1,3],[2],[2,3],[3]]
想得到的全排列输出：[[],[1],[2],[3],[1,2],[1,3],[2,3],[1,2,3]]

backtrack函数中通过设置参数k对长度进行限制

• k < 0：说明长度超过设置的长度直接退出
• k = 0: 长度正好，添加到结果集中
• k > 0：还有元素未加入到track中，继续进行回溯
  其次在主函数中也要加入循环，

  for(int i = 0; i <= S.length; i++)
        backtrack(S, track, 0, i);

  这样可以控制先从长度小的结果开始算。

代码如下：

import java.util.*;
public class Solution {
    ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
    public ArrayList<ArrayList<Integer>> subsets(int[] S) {
        ArrayList<Integer> track = new ArrayList<>();
        for(int i = 0; i <= S.length; i++)
            backtrack(S, track, 0, i);
        return res;
    }
    public void backtrack(int[] S, ArrayList<Integer> track ,int index, int k) {
        if (k < 0)
            return;
        else if (k == 0)
            res.add(new ArrayList(track));
        else {
            for(int i = index; i < S.length; i++) {
                track.add(S[i]);
                backtrack(S, track, i + 1, k - 1);
                track.remove(track.size() - 1);
            }
        }

    }
}