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哈希