回溯算法（backtracking ）解决子集和、全排列、组合数之和等问题

目录

  • LeetCode 78. Subsets
    • 回溯解法
    • 递归解法
  • LeetCode 90. Subsets II
    • 回溯解法
    • 递归解法
  • LeetCode 46. Permutations
  • LeetCode 47. Permutations II
  • LeetCode 784. Letter Case Permutation
  • LeetCode 39. Combination Sum
  • LeetCode 40. Combination Sum II
  • LeetCode 131. Palindrome Partitioning
  • 回溯问题一般解法

LeetCode 78. Subsets

题目要求

Given a set of distinct integers, nums, return all possible subsets (the power set).

Note: The solution set must not contain duplicate subsets.

  • 参数数组中无重复数字
  • 结果集中要求无重复子集

回溯解法

class Solution78_1 {
    List<List<Integer>> ret = new ArrayList<>();
    public List<List<Integer>> subsets(int[] nums) {
        if(nums == null) return ret;
        ArrayList<Integer> list = new ArrayList<>();
        dfs(nums, 0, list);
        return ret;
    }
    public void dfs(int[] nums, int start, ArrayList<Integer> list){
        ret.add(new ArrayList<>(list));
        for(int i = start; i < nums.length; i++){
            list.add(nums[i]);
            dfs(nums, i+1, list);
            list.remove(list.size() - 1);
        }
    }
}

另一种风格的dfs+回溯，更好理解，但会稍微慢一些。

class Solution78 {
    List<List<Integer>> ret = new ArrayList<>();
    public List<List<Integer>> subsets(int[] nums) {
        if(nums == null) return ret;
        ArrayList<Integer> list = new ArrayList<>();
        backtrack(nums, 0, list);
        return ret;
    }
    public void backtrack(int[] nums, int offset, ArrayList<Integer> list){
        if(offset == nums.length){
            ret.add(new ArrayList<>(list));
            return;
        }
        backtrack(nums, offset+1, list);
        list.add(nums[offset]);
        backtrack(nums, offset+1, list);
        list.remove(list.size() - 1);
    }
}

递归解法

很多回溯问题可以用递归解决，所以我就将我写的递归贴出来吧
也叫BFS（？）。
思路：
当我们遍历数组中的每一个元素，我们可以选择也可以不选择：

  • 如果我们不选择，那么就保持结果集中不变。
  • 如果我们选择，那么就出现已有结果集中的所有子集分别加上这个元素，就生成了包含这个元素的新的子集；
    将以上两种情况加起来就是对当前元素处理过的新的结果集。
    对了，因为空集 [], 也是符合的，并且我们要使用它对结果集初始化。{[]}
    比如对于数组{1， 2， 3}，遍历到第一个元素后结果集为 {[], [1]}, 遍历到第二元素结果集变为：{[], [1], [2], [1, 2]}, 以此类推。
class Solution78_2 {
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> ret = new ArrayList<>();
        ret.add(new ArrayList<Integer>());
        for(int i = 0; i < nums.length; i++){
            int size = ret.size();
            for(int j = 0; j < size; j++){
                ArrayList<Integer> temList = new ArrayList<>(ret.get(j));
                temList.add(nums[i]);
                ret.add(temList);
            }
        }
        return ret;
    }
}

LeetCode 90

回溯解法

参数数组中可能含有重复数字（这是与上一题(78)中不一样的地方）：

  1. 子集中可以有重复数字，但返回的结果中不能含有相同的子集 所以我们用直接用链表作为结果集就有可能使前后两个相同的子集先后放入，导致出现重复子集，因此这里我们使用set作为结果集，以免相同子集加入，返回时转化为链表
  2. 此外，由于参数提供的数组并不是有序的，这就导致出现很多含有相同数据集但顺序不同的子集，所以，我们可以在dfs前对数组进行一个排序，这样可以保证只要两个子集包含相同的数字，那么他们的顺序也会相同，故不可以连续加入结果集中
class Solution90{
    Set<List<Integer>> ret = new HashSet<>();
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        if(nums == null) return new ArrayList<>();
        ArrayList<Integer> list = new ArrayList<>();
        Arrays.sort(nums);
        dfs(nums, 0, list);
        return new ArrayList<>(ret);
    }

    public void dfs(int[] nums, int offset, ArrayList<Integer> list){
        if(offset == nums.length){
            // Collections.sort(list);
            ret.add(new ArrayList<>(list));
            return;
        }
        dfs(nums, offset+1, list);
        list.add(nums[offset]);
        dfs(nums, offset+1, list);
        list.remove(list.size() - 1);
    }
}

for循环方式回溯

class Solution90_1 {
    ArrayList<List<Integer>> ret = new ArrayList<>();
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        if(nums == null) return new ArrayList<>();
        ArrayList<Integer> list = new ArrayList<>();
        Arrays.sort(nums);
        dfs(nums, 0, list);
        return ret;
    }
    public void dfs(int[] nums, int start, ArrayList<Integer> list){
        ret.add(new ArrayList<>(list));
        for(int i = start; i < nums.length; i++){
            if(i != start && nums[i] == nums[i - 1]) continue;
            list.add(nums[i]);
            dfs(nums, i+1, list);
            list.remove(list.size() - 1);
        }
    }
}

递归解法

我们再用递归的方式做一下，因为数组中包含重复数字，所以我们遍历时，如果第i个元素和第i+1个元素相同，就会出现重复。

比如数组{1， 2， 2}

初始 ：{[]}
第1个元素：{[], [1]}

第2个元素：{[], [1], [2], [1, 2]}
第3个元素：{[], [1], [2], [1, 2]，[2], [1, 2], [2, 2], [1, 2, 2]} //出现重复

那么规避的方式也很简单：当我们判断出当前元素和上一个元素相同时，我们仅仅将其插入到上一步生成的元素。
对应上面的例子就是仅仅将其插入或不插入这些子集：{[2], [1, 2]}

那么遍历完第3个元素后的正确结果应该是：{[], [1], [2], [1, 2], [2, 2], [1, 2, 2]}

class Solution90_2 {
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>> ret = new ArrayList<>();
        ret.add(new ArrayList<Integer>());
        int preIndex = 1;
        for(int i = 0; i < nums.length; i++){
            int size = ret.size();
            int j = 0;
            if(i != 0 && nums[i] == nums[i - 1]) j = preIndex;
            for(; j < size; j++){
                ArrayList<Integer> temList = new ArrayList<>(ret.get(j));
                temList.add(nums[i]);
                ret.add(temList);
            }
            preIndex = size;
        }
        return ret;
    }
}

LeetCode 46. Permutations

题目要求：给定一个不包含重复数字的数据集，要求返回这个数据集的全排列。
思路：
整体还是一个 dfs+回溯 的思路
用一个链表存储新加入的数字，当链表长度等于数组长度，表明生成一个新的排列
由于原数据集(数组）中无重复数字)，那么我们在判断一个数字是否已经加入时就可以直接判断链表中是否已经包含这个数字，若不包含，则证明还没加入；
但是，当遇到数据集中含有重复数字的时候，就不可以这样判断了，因为一个数字可能有两次或多次，当我们判断链表中已经有了这个数字，那这个数字第二次出现就五分啊加入，
这时候我们可以用一个标记数组(boolean类型的数组)标记每个数字是否已经加入。

class Solution46 {
    List<List<Integer>> ret = new ArrayList<>();
    public List<List<Integer>> permute(int[] nums) {
        if(nums == null) return ret;
        dfs(nums, new ArrayList<Integer>());
        return ret;
    }
    public void dfs(int[] nums, ArrayList<Integer> list){
        if(list.size() == nums.length){
            ret.add(new ArrayList<>(list));
            return;
        }
        for(int i = 0; i < nums.length; i++){
            if(list.contains(nums[i])) continue;
            list.add(nums[i]);
            dfs(nums, list);
            list.remove(list.size() - 1);
        }
    }
}

LeetCode 47. Permutations II

题目要求：给定一个可能含重复数字的数据集，要求返回这个数据集的全排列。
思路：
整体还是一个 dfs+回溯 的思路
用一个链表存储新加入的数字，当链表长度等于数组长度，表明生成一个新的排列
遇到数据集中含有重复数字的时候，就不可以这样判断了，因为一个数字可能有两次或多次，当我们判断链表中已经有了这个数字，那这个数字第二次出现就五分啊加入，
这时候我们可以用一个标记数组(boolean类型的数组)标记每个数字是否已经加入。
两外需要注意的是，当遇到两个重复的数据，先加入a后加入b和先加入b后加入a会出现相同的排列，所以需要使用集合类型保存结果集，防止重复排列加入。

class Solution47 {
    Set<List<Integer>> ret = new HashSet<>();
    public List<List<Integer>> permuteUnique(int[] nums) {
        if(nums == null) return new ArrayList<>();
        boolean[] visited = new boolean[nums.length];
        dfs(nums, new ArrayList<Integer>(), visited);
        return new ArrayList<>(ret);
    }

    public void dfs(int[] nums, ArrayList<Integer> list, boolean[] visited){
        if(list.size() == nums.length){
            ret.add(new ArrayList<>(list));
            return;
        }

        for(int i = 0; i < nums.length; i++){
            if(visited[i]) continue;
            list.add(nums[i]);
            visited[i] = true;
            dfs(nums, list, visited);
            list.remove(list.size() - 1);
            visited[i] = false;
        }
    }
}

for循环方式回溯
好处：可以在遍历时就对重复情况进行处理

class Solution47_1 {
    List<List<Integer>> ret = new ArrayList<>();
    public List<List<Integer>> permuteUnique(int[] nums) {
        Arrays.sort(nums);
        boolean[] visited = new boolean[nums.length];
        dfs(nums, new ArrayList<Integer>(), visited);
        return ret;
    }
    public void dfs(int[] nums, ArrayList<Integer> list, boolean[] visited){
        if(list.size() == nums.length){
            ret.add(new ArrayList<>(list));
            return;
        }
        for(int i = 0; i < nums.length; i++){
            if(visited[i]) continue;
            if(i != 0 && nums[i] == nums[i - 1] && !visited[i - 1])continue;
            list.add(nums[i]);
            visited[i] = true;
            dfs(nums, list, visited);
            list.remove(list.size() - 1);
            visited[i] = false;
        }
    }
}

LeetCode 784. Letter Case Permutation

题目要求：给定一个字符串，将其中的字母变为大写或者小写可以变成另一个字符串，要求返回所有可能的字符串的集合。
思路：典型的dfs+回溯，只是在每次处理时需要判断此处的字符是字母还是数字，数字直接追加，字母则可以分为大写和小写。

class Solution784 {
    List<String> ret = new ArrayList<>();
    public List<String> letterCasePermutation(String S) {
        if(S == null) return ret;
        String str = "";
        dfs(S, 0, str);
        return ret;
    }

    public void dfs(String S, int offset, String str){
        if(offset == S.length()){
            ret.add(str);
            return;
        }
        char c = S.charAt(offset);
        if(c >= '0' && c <= '9') {
            dfs(S, offset + 1, str + c);
        }
        if(c >= 'a' && c <= 'z'){
            dfs(S, offset + 1, str + c);
            dfs(S, offset + 1, str + (char)(c - 32));
        }
        if(c >= 'A' && c <= 'Z'){
            dfs(S, offset + 1, str + (char)(c + 32));
            dfs(S, offset + 1, str + c);
        }
        return;
    }
}

LeetCode 39. Combination Sum

题目要求：给一个无重复数字的候选数据集和一个目标数字，要求从候选数据集中选出相加的和等于目标数字的数据集的所有情况，候选数据集中的数字可以被重复使用。
思路：
这还是一个“组合”问题，对于每个元素，选还是不选，对于计算机来说当然是每种情况都要考虑，所以我们依然考虑dfs+回溯的思想，但是本题中每个数字可以被重复使用，dfs考虑起来不是那么方便。所以我们换一种方式。
采用迭代+dfs+回溯的方式。也就是for循环方式的回溯。
dfs每次需要一个起使偏移量，那么我们每次递归的时候将起使偏移量设置为原值就实现了数字的重复使用。

class Solution39 {
    List<List<Integer>> ret = new ArrayList<>();
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        Arrays.sort(candidates);
        backtrack(candidates, target, 0, new ArrayList<>());
        return ret;
    }
    public void backtrack(int[] candidates, int target, int start, ArrayList<Integer> list){
        if(target < 0) return;
        if(target == 0){
            ret.add(new ArrayList<>(list));
            return;
        }
        for(int i = start; i < candidates.length; i++){
            list.add(candidates[i]);
            backtrack(candidates, target - candidates[i], i, list); // 不用start+1, 因为每个数可以重复使用
            list.remove(list.size() - 1);
        }
    }
}

LeetCode 40. Combination Sum II

本题是39题的变种，和 39 题有两点不同：

    1. 提供的候选数可能重复；
    1. 每个数字不可重复使用。
      因此做出相应修改就可以。
class Solution40 {
    Set<List<Integer>> ret = new HashSet<>();
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        Arrays.sort(candidates);
        backtrack(candidates, target, 0, new ArrayList<>());
        return new ArrayList<>(ret);
    }
    public void backtrack(int[] candidates, int target, int start, ArrayList<Integer> list){
        if(target < 0) return;
        if(target == 0){
            ret.add(new ArrayList<>(list));
            return;
        }
        for(int i = start; i < candidates.length; i++){
            list.add(candidates[i]);
            backtrack(candidates, target - candidates[i], i + 1, list); // 不用start+1, 因为每个数可以重复使用
            list.remove(list.size() - 1);
        }
    }
}

每个数字不可重复修改还可以通过另一种方式：
for 循环的目的是: 每次循环找出以第i个数字开始的序列，所以当第i个数字和第i-1个数字相同时，由于后续的回溯处理是一样的，就会生成一系列重复的序列
因此，这种情况下可以直接跳过：

class Solution401 {
    List<List<Integer>> ret = new ArrayList<>();
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        Arrays.sort(candidates);
        backtrack(candidates, target, 0, new ArrayList<>());
        return ret;
    }
    public void backtrack(int[] candidates, int target, int start, ArrayList<Integer> list){
        if(target < 0) return;
        if(target == 0){
            ret.add(new ArrayList<>(list));
            return;
        }
        for(int i = start; i < candidates.length; i++){
            if(i > start && candidates[i] == candidates[i-1]) continue;
            list.add(candidates[i]);
            backtrack(candidates, target - candidates[i], i + 1, list); // 不用start+1, 因为每个数可以重复使用
            list.remove(list.size() - 1);
        }
    }
}

当然这种数字不重复使用的，也可以用我们笨笨的dfs+回溯，那就要考set去重了

class Solution402 {
    Set<List<Integer>> ret = new HashSet<>();
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        Arrays.sort(candidates);
        backtrack(candidates, target, 0, new ArrayList<>());
        return new ArrayList<>(ret);
    }
    public void backtrack(int[] candidates, int target, int offset, ArrayList<Integer> list){
        if(target == 0){
            ret.add(new ArrayList<>(list));
            return;
        }
        if(target < 0 || offset >= candidates.length) return;
        backtrack(candidates, target, offset + 1, list);
        list.add(candidates[offset]);
        backtrack(candidates, target - candidates[offset], offset + 1, list);
        list.remove(list.size() - 1);
    }
}

LeetCode 131. Palindrome Partitioning

题目要求：将一个给定的字符串，分割成若干个子字符串，使得每一个字符串都为回文字符串，返回所有的分割情况。

class Solution131 {
    List<List<String>> ret = new ArrayList<>();
    public List<List<String>> partition(String s) {
        backtrack(s, 0, new ArrayList<String>());
        return ret;
    }
    public void backtrack(String s, int start, ArrayList<String> list)
    {
        if(start == s.length()){
            ret.add(new ArrayList<>(list));
            return;
        }
        for(int i = start; i < s.length(); i++){
            if(isPalindrome(s, start, i)){
                list.add(s.substring(start, i + 1));
                backtrack(s, i + 1, list);
                list.remove(list.size() - 1);
            }
        }
    }
    public boolean isPalindrome(String s, int l, int h){
        while(l < h){
            if(s.charAt(l) != s.charAt(h)) return false;
            l++;
            h--;
        }
        return true;
    }
}

回溯问题一般解法

// 回溯思想解法一般可以归纳为以下思路：
int start = x;   // 选择一个合适的起点
while(问题未被解决/所获临时结果未达到有效)
    for(从start端可以进行的所有路径){
        判断进行这条路径是否合法;
        合法就做相应处理；
        递归调用处理剩下的部分；
          恢复到处理前的状态；
      }
返回结果集；

回溯问题的很多变种还是很有意思的，一般也能用递归方式解决。本文将继续完善。

©著作权归作者所有,转载或内容合作请联系作者
  • 人面猴
    序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
    沈念sama阅读 217,734评论 6赞 505
  • 死咒
    序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
    沈念sama阅读 92,931评论 3赞 394
  • 救了他两次的神仙让他今天三更去死
    文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
    开封第一讲书人阅读 164,133评论 0赞 354
  • 道士缉凶录：失踪的卖姜人
    文/不坏的土叔 我叫张陵，是天一观的道长。 经常有香客问我，道长，这世上最难降的妖魔是什么？ 我笑而不...
    开封第一讲书人阅读 58,532评论 1赞 293
  • 港岛之恋（遗憾婚礼）
    正文 为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
    茶点故事阅读 67,585评论 6赞 392
  • 恶毒庶女顶嫁案：这布局不是一般人想出来的
    文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
    开封第一讲书人阅读 51,462评论 1赞 302
  • 城市分裂传说
    那天，我揣着相机与录音，去河边找鬼。 笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。 我是一名探鬼主播，决...
    沈念sama阅读 40,262评论 3赞 418
  • 双鸳鸯连环套：你想象不到人心有多黑
    文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
    开封第一讲书人阅读 39,153评论 0赞 276
  • 万荣杀人案实录
    序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
    沈念sama阅读 45,587评论 1赞 314
  • 护林员之死
    正文 独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 37,792评论 3赞 336
  • 白月光启示录
    正文 我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 39,919评论 1赞 348
  • 活死人
    序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
    沈念sama阅读 35,635评论 5赞 345
  • 日本核电站爆炸内幕
    正文 年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
    茶点故事阅读 41,237评论 3赞 329
  • 男人毒药：我在死后第九天来索命
    文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 31,855评论 0赞 22
  • 一桩弑父案，背后竟有这般阴谋
    文/苍兰香墨 我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 32,983评论 1赞 269
  • 情欲美人皮
    我被黑心中介骗来泰国打工， 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。 一个月前我还...
    沈念sama阅读 48,048评论 3赞 370
  • 代替公主和亲
    正文 我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
    茶点故事阅读 44,864评论 2赞 354

推荐阅读更多精彩内容