leetcode回溯算法总结

17. 电话号码的字母组合

46. 全排列

47. 全排列 II

39. 组合总和

40. 组合总和 II

491. 递增子序列

77. 组合

78. 子集

90. 子集 II

60. 排列序列

784. 字母大小写全排列

22. 括号生成

51. N 皇后

491. 递增子序列

93. 复原 IP 地址

回溯算法入门级详解 + 练习（持续更新）

文章目录

- 17. 电话号码的字母组合
- 46. 全排列
- 47. 全排列 II
- 39. 组合总和
- 40. 组合总和 II
- 77. 组合
- 78. 子集
- 90. 子集 II
- 60. 排列序列
- 784. 字母大小写全排列
- 22. 括号生成
- 51. N 皇后
- 491. 递增子序列
- 93. 复原 IP 地址

17. 电话号码的字母组合

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按任意顺序返回。

给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

class Solution {
    public List<String> letterCombinations(String digits) {
        List<String> list=new ArrayList<>();
        StringBuffer strbf=new StringBuffer();
        if(digits==null||digits.length()<=0)
        return list;
        Map<Character,String> map=new HashMap<>();
        map.put('2',"abc");map.put('3',"def");map.put('4',"ghi");
        map.put('5',"jkl");map.put('6',"mno");map.put('7',"pqrs");
        map.put('8',"tuv");map.put('9',"wxyz");
        backTrack(list,digits,map,strbf,0);
        return list;
    }
    private void backTrack(List<String> list,String digits,Map<Character,String> map,StringBuffer strbf,int index){
        if(index==digits.length()){
            list.add(strbf.toString());
            return;
        }
        String str=map.get(digits.charAt(index));
        for(int i=0;i<str.length();i++){
            strbf.append(str.charAt(i));
            backTrack(list,digits,map,strbf,index+1);
            strbf.deleteCharAt(index);
        }
    }
}

46. 全排列

给定一个没有重复数字的序列，返回其所有可能的全排列。

class Solution {
    public List<List<Integer>> permute(int[] nums) {
        List<Integer> list = new ArrayList<>();
        List<List<Integer>> res=new ArrayList<>();
        int n=nums.length;
        boolean[] isused=new boolean[n];
        backTrack(nums,list,res,0,n,isused);
        return res;
    }
    private void backTrack(int[] nums,List<Integer>list,List<List<Integer>> res,int index,int n,boolean[] isused){
        if(index==n){
            res.add(new ArrayList<>(list));
            return;
        }
        for(int i=0;i<n;i++){
            if(isused[i]==false){
                isused[i]=true;
                list.add(nums[i]);
                backTrack(nums,list,res,index+1,n,isused);
                isused[i]=false;
                list.remove(list.size()-1);
            }
        }
    }
}

47. 全排列 II

给定一个可包含重复数字的序列 nums ，按任意顺序返回所有不重复的全排列。

差解：用了一个Set判断

class Solution {
    public List<List<Integer>> permuteUnique(int[] nums) {
        List<Integer> list = new ArrayList<>();
        List<List<Integer>> res=new ArrayList<>();
        Set<List<Integer>> set=new HashSet<>();
        int n=nums.length;
        boolean[] isused=new boolean[n];
        backTrack(nums,list,set,0,n,isused);
        return new ArrayList(set);
    }
    private void backTrack(int[] nums,List<Integer>list,Set<List<Integer>> res,int index,int n,boolean[] isused){
        if(index==n){
            res.add(new ArrayList<>(list));
            return;
        }
        for(int i=0;i<n;i++){
            if(isused[i]==false){
                isused[i]=true;
                list.add(nums[i]);
                backTrack(nums,list,res,index+1,n,isused);
                isused[i]=false;
                list.remove(list.size()-1);
            }
        }
    }
}

优解：

class Solution {
    public List<List<Integer>> permuteUnique(int[] nums) {
        List<Integer> list = new ArrayList<>();
        List<List<Integer>> res=new ArrayList<>();  
        Arrays.sort(nums);
        int n=nums.length;
        boolean[] isused=new boolean[n];//这个是说当前位置的元素是否被使用过
        backTrack(nums,list,res,0,n,isused);
        return res;
    }
    private void backTrack(int[] nums,List<Integer>list,List<List<Integer>> res,int index,int n,boolean[] isused){
        if(index==n){
            res.add(new ArrayList<>(list));
            return;
        }
        for(int i=0;i<n;i++){
            if(isused[i]||(i>0&&nums[i]==nums[i-1]&&!isused[i-1]))//可能会疑惑这里为什么要加isused[i-1}
            continue;
            isused[i]=true;
            list.add(nums[i]);
            backTrack(nums,list,res,index+1,n,isused);
            isused[i]=false;
            list.remove(list.size()-1);
            
        }
    }
}

当看了下面的组合总和II后可能会疑惑为什么要加这一句话。

这是因为我们这里的插入空隙的选择是从0开始的，而下面的题是从index开始的。

即区别以下两种状况：

—— —— ——

1.1(第一个一) 1.2 2

1.2(第二个一) 1.1 2

当从下标0开始选择，选择1.1，然后进入下一个位置(第二个位置)进行选择，而如果不写上isused[i-1]这句话的话，则会无法选择1.2

而(i>0&&nums[i]==nums[i-1)这句话的作用，就是为了让第一个位置无法选择1.2.

意思是，前一句是为了让第一个位置无法选择1.2，后一句是为了让第二个位置可以选择1.2.可以与组合综合II对比一下。

39. 组合总和

给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。

candidates 中的数字可以无限制重复被选取。

说明：

所有数字（包括 target）都是正整数。

解集不能包含重复的组合。

class Solution {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<Integer> list=new ArrayList<>();
        List<List<Integer>> res=new ArrayList<>();
        backTack(candidates,target,0,list,res,0);
        return res;
    }
    private void backTack(int[] candidates,int target,int sum,List<Integer> list,List<List<Integer>> res,int index){
        if(sum==target){
            res.add(new ArrayList<>(list));
            return;
        }
        if(sum>target)
        return;
        for(int i=index;i<candidates.length;i++){
            list.add(candidates[i]);
            backTack(candidates,target,sum+candidates[i],list,res,i);
            list.remove(list.size()-1);
        }
    }

}

40. 组合总和 II

给定一个数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。

candidates 中的每个数字在每个组合中只能使用一次。

说明：

所有数字（包括目标数）都是正整数。

解集不能包含重复的组合。

出现重复解：

class Solution {
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        List<Integer> list=new ArrayList<>();
        List<List<Integer>> res=new ArrayList<>();
        backTack(candidates,target,list,res,0,0);
        return res;
    }
    private void backTack(int[] candidates,int target,List<Integer>list,List<List<Integer>> res,int sum,int index){
        if(sum==target){
            res.add(new ArrayList<>(list));
            return;
        }
        if(sum>target||index==candidates.length){
            return;
        }
        for(int i=index;i<candidates.length;i++){
            list.add(candidates[i]);
            backTack(candidates,target,list,res,sum+candidates[i],i+1);
            list.remove(list.size()-1);
        }
    }
}

无重复解：

class Solution {
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        List<Integer> list=new ArrayList<>();
        List<List<Integer>> res=new ArrayList<>();
        Arrays.sort(candidates);//排序
        backTack(candidates,target,list,res,0,0);
        return res;
    }
    private void backTack(int[] candidates,int target,List<Integer>list,List<List<Integer>> res,int sum,int index){
        if(sum==target){
            res.add(new ArrayList<>(list));
            return;
        }
        if(sum>target||index==candidates.length){
            return;
        }
        for(int i=index;i<candidates.length;i++){
            if(i>index&&candidates[i]==candidates[i-1])//判断
            continue;
            list.add(candidates[i]);
            backTack(candidates,target,list,res,sum+candidates[i],i+1);//当index=i+1时，是不允许当前元素再次使用的，而当index=i时，是允许当前元素再次使用的
            list.remove(list.size()-1);
        }
    }
}

if(i>index&&candidates[i]==candidates[i-1])//判断
 continue;

可以将这一句理解为：

插入当前位置的时候，只能插一次

因为回溯算法和空白位置插入是差不多的。

如： —— —— —— (1,2,2)在这三个位置上进行计算求和

第一个位置可以是1，第二个位置可以是2.1(第一个二),也可以是2.2(第二个二）

在这种情况下就会产生：

1，2.1，2.2

1，2.2，2.1

这样的重复，但，加入我们在第二个位置加上限定：不允许插入和前一个元素相同的元素，那么，2.2就无法插入到第二个位置了。

就只会有1，2.1，2.2这一种选择。

77. 组合

给定两个整数 n 和 k，返回 1 … n 中所有可能的 k 个数的组合。

class Solution {
    public List<List<Integer>> combine(int n, int k) {
        List<Integer> list=new ArrayList<>();
        List<List<Integer>> res=new ArrayList<>();
        backTack(n,k,list,res,1,0);
        return res;
    }
    private void backTack(int n,int k,List<Integer> list, List<List<Integer>> res,int begin,int len){
        if(len==k){
            res.add(new ArrayList<>(list));
            return;
        }
        for(int i=begin;i<=n;i++){
            list.add(i);
            backTack(n,k,list,res,i+1,len+1);
            list.remove(list.size()-1);
        }
    }
}

78. 子集

给你一个整数数组 nums ，数组中的元素互不相同。返回该数组所有可能的子集（幂集）。

解集不能包含重复的子集。你可以按任意顺序返回解集。

class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        List<Integer> list=new ArrayList<>();
        List<List<Integer>> res=new ArrayList<>();
        backTack(nums,0,0,list,res);
        return res;
    }
    private void backTack(int[] nums,int index,int len,List<Integer> list,List<List<Integer>> res){
        if(len>nums.length)
        return;
        res.add(new ArrayList<>(list));
        for(int i=index;i<nums.length;i++){
            list.add(nums[i]);
            backTack(nums,i+1,len+1,list,res);
            list.remove(list.size()-1);
        }
        
    }
}

90. 子集 II

给你一个整数数组 nums ，其中可能包含重复元素，请你返回该数组所有可能的子集（幂集）。

解集不能包含重复的子集。返回的解集中，子集可以按任意顺序排列。

class Solution {
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        List<Integer> list=new ArrayList<>();
        List<List<Integer>> res=new ArrayList<>();
        boolean[] isused=new boolean[nums.length];
        Arrays.sort(nums);
        backTack(nums,list,res,0,0,isused);
        return res;
    }
    private void backTack(int[] nums,List<Integer> list, List<List<Integer>> res,int index,int len,boolean[] isused){
        if(len>nums.length)
        return;
        res.add(new ArrayList<>(list));
        for(int i=index;i<nums.length;i++){
            if(i>0&&nums[i]==nums[i-1]&&!isused[i-1])
            continue;
            isused[i]=true;
            list.add(nums[i]);
            backTack(nums,list,res,i+1,len+1,isused);
            list.remove(list.size()-1);
            isused[i]=false;
        }
    }
}

60. 排列序列

给出集合 [1,2,3,…,n]，其所有元素共有 n! 种排列。

按大小顺序列出所有排列情况，并一一标记，当 n = 3 时, 所有排列如下：

“123”

“132”

“213”

“231”

“312”

“321”

给定 n 和 k，返回第 k 个排列。

class Solution {
    String str;
    int sum=0;
    public String getPermutation(int n, int k) {
        boolean[] isused=new boolean[n];
        backTrack(n,k,0,isused,new StringBuffer());
        return str;
    }
    private void backTrack(int n,int k,int index,boolean[] isused,StringBuffer sb){
        if(sum==k)
        return;
        if(index==n){
            sum++;
            if(sum==k){
                str=sb.toString();
                return;
            }
        }
        for(int i=0;i<n;i++){
            if(isused[i])
            continue;
            isused[i]=true;
            sb.append(Integer.toString(i+1));
            backTrack(n,k,index+1,isused,sb);
            sb.deleteCharAt(sb.length()-1);
            isused[i]=false;
        }

    }
}

784. 字母大小写全排列

给定一个字符串S，通过将字符串S中的每个字母转变大小写，我们可以获得一个新的字符串。返回所有可能得到的字符串集合。

示例：

输入：S = “a1b2”

输出：[“a1b2”, “a1B2”, “A1b2”, “A1B2”]

输入：S = “3z4”

输出：[“3z4”, “3Z4”]

输入：S = “12345”

输出：[“12345”]

class Solution {
    public List<String> letterCasePermutation(String S) {
        List<String> list=new ArrayList<>();
        backTrack(S,0,new StringBuffer(),list);
        return list;

    }
    private void backTrack(String s,int index,StringBuffer sb,List<String> list){
        if(index==s.length()){
            list.add(sb.toString());
            return;
        }
        if(s.charAt(index)>='0'&&s.charAt(index)<='9'){
            sb.append(s.charAt(index));
            backTrack(s,index+1,sb,list);
            sb.deleteCharAt(sb.length()-1);
            return;
        }

        char c=helper(s.charAt(index));
        sb.append(c);
        backTrack(s,index+1,sb,list);
        sb.deleteCharAt(sb.length()-1);

        sb.append(s.charAt(index));
        backTrack(s,index+1,sb,list);
        sb.deleteCharAt(sb.length()-1);
    }
    private char helper(char c){
        if(c>='A'&&c<='Z')
        return Character.toLowerCase(c);
        else
        return Character.toUpperCase(c);
    }
}

22. 括号生成

数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且有效的括号组合。

示例 1：

输入：n = 3

输出：["((()))","(()())","(())()","()(())","()()()"]

示例 2：

输入：n = 1

输出：["()"]

class Solution {
    public List<String> generateParenthesis(int n) {
        List<String> list=new ArrayList<>();
        backTrack(n,new StringBuffer(),list,0,0);
        return list;
    }
    private void backTrack(int n,StringBuffer sb,List<String> list,int left,int right){
        if(left>n||right>n||left<right)
        return;
        if(left==n&&right==n){
            list.add(sb.toString());
            return;
        }
        sb.append("(");
        backTrack(n,sb,list,left+1,right);
        sb.deleteCharAt(sb.length()-1);
        sb.append(")");
        backTrack(n,sb,list,left,right+1);
        sb.deleteCharAt(sb.length()-1);
    }
}

51. N 皇后

n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。

给你一个整数 n ，返回所有不同的 n 皇后问题的解决方案。

每一种解法包含一个不同的 n 皇后问题的棋子放置方案，该方案中 ‘Q’ 和 ‘.’ 分别代表了皇后和空位。

491. 递增子序列

给定一个整型数组, 你的任务是找到所有该数组的递增子序列，递增子序列的长度至少是 2 。

示例：

输入：[4, 6, 7, 7]

输出：[[4, 6], [4, 7], [4, 6, 7], [4, 6, 7, 7], [6, 7], [6, 7, 7], [7,7], [4,7,7]]

93. 复原 IP 地址

给定一个只包含数字的字符串，用以表示一个 IP 地址，返回所有可能从 s 获得的有效 IP 地址。你可以按任何顺序返回答案。

有效 IP 地址正好由四个整数（每个整数位于 0 到 255 之间组成，且不能含有前导 0），整数之间用 ‘.’ 分隔。

例如：“0.1.2.201” 和 “192.168.1.1” 是有效 IP 地址，但是 “0.011.255.245”、“192.168.1.312” 和 “[email protected]” 是无效 IP 地址。

leetcode回溯算法总结

文章目录

17. 电话号码的字母组合

46. 全排列

47. 全排列 II

39. 组合总和

40. 组合总和 II

77. 组合

78. 子集

90. 子集 II

60. 排列序列

784. 字母大小写全排列

22. 括号生成

51. N 皇后

491. 递增子序列

93. 复原 IP 地址

继续阅读

Java String.format方法的简单使用

neo4j之cypher使用文档

Dijkstra--简易版（最短路径）

GitHub连夜封杀！这份阿里 10W 字内部 Java 字面试手册到底有多强？

spark/scala关于【资源文件】加载方法概述外部文件加载方案测试资源文件打包入jar包中小结

mybatis_入门程序Mybatis入门

AOP编程_Android优雅权限框架(1)概念基础，2021金三银四前言正文大纲正文

LeetCode OJ Binary Tree Right Side View

Effective Java 8:通用程序设计

leetcode809

OOM三种类型

工厂模式-三种类型

【递归】高效率求2的n次幂

win10本地scala和spark安装安装scala安装spark

scala (3) Function 和 Method

hdu7108哈希