回溯法

回溯法動態(tài)規(guī)劃題目
https://www.cnblogs.com/jiangchen/p/5930049.html
回溯法概念（http://www.cnblogs.com/jiangchen/p/5393849.html）

LeetCode 39. Combination Sum （組合的和）

Given a set of candidate numbers (C) (without duplicates) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.

The same repeated number may be chosen from C unlimited number of times.

Note:

  • All numbers (including target) will be positive integers.
  • The solution set must not contain duplicate combinations.

For example, given candidate set [2, 3, 6, 7] and target 7,
A solution set is:

<pre style="margin: 0px; padding: 0px; white-space: pre-wrap; word-wrap: break-word;">[
[7],
[2, 2, 3]
]</pre>
題目標簽：Array

題目給了我們一個candidates array 和一個 target， 讓我們從array 里找到所有的組合，它的和是等于target的。任何組合只要是它的和等于target的話，都需要找到，但是不需要重復的。這道題中是可以重復利用一個數字的，那么我們就需要每次都代入同一個數字，直到它之和達到target 或者它超過了target， 然后在倒退回去一個數字，繼續(xù)找下一個數字，這種情況肯定是要用遞歸了。這里是backtracking，每次倒退回一個數字，需要繼續(xù)遞歸下去，在倒退，一直重復直到搜索了所有的可能性。

我們可以看原題中的例子：

[2,3,6,7] target 7

2 選2，sum = 2

2+2 選2，sum = 4

2+2+2 選2，sum = 6

2+2+2+2 選2，sum = 8 這時候 sum已經超出target，需要返回到上一個數字

2+2+2+3 選3，sum = 9， 也超出了target， 這里我們可以發(fā)現(xiàn)，如果是sorted array的話，從小到大，只要一次超出，后面的數字必然也會超出target，所以可以在第一次超出的時候就直接跳出這一個迭代

2+2+3 選3，sum = 7，等于target， 此時返回并且跳出這一個迭代，因為后面的數字肯定超出（array里不會有重復的數字）

2+3 選3，sum = 5，小于target，繼續(xù)遞歸同一個數字

2+3+3 選3，sum = 8，超出target，返回上一個數字

2+6 選6，sum = 8，超出target，返回上一個數字

3 選3，這里繼續(xù)從3開始遞歸

...

...

...

我們可以看出，一開始有一個迭代從2，一直到7，然后把每一個數字遞歸下去，包括它自己，每次遞歸下去的數字，會繼續(xù)有一個迭代，一旦超出或者等于了，返回前面一個數字繼續(xù)遞歸。所以把array sort一下就可以提早跳出那一輪的迭代。
數組中的每個數字可以用多次：

public List<List<Integer>>  getAllCombination(int[] arr,int target){
        List<List<Integer>> resList=new ArrayList<List<Integer>>();
        List<Integer> curList=new ArrayList<>();
        Arrays.sort(arr);
        backTracking(resList,curList,arr,target,0);
        return resList;
    }

    /**
     * @param resList
     * @param curList
     * @param arr
     * @param target
     * @param i
     *<p>Description: </p>  
     */
    private boolean backTracking(List<List<Integer>> resList,
            List<Integer> curList, int[] arr, int remain, int start) {

        if(remain==0){
            resList.add(new ArrayList<Integer>(curList));
            return false;
        }
        if(remain<0){
            return false;
        }
        else{
            for(int i=start;i<arr.length;i++){
                curList.add(arr[i]);
                boolean flag=backTracking(resList, curList, arr, remain-arr[i], i);
                curList.remove(curList.size()-1);
                if(!flag){
                    break;
                }
            }
            return true;

        }
    }

如果數組中不包含重復的元素的，且每個元素只能用一次。

public List<List<Integer>>  getAllCombinationUnduplicate(int[] arr,int target){
        List<List<Integer>> resList=new ArrayList<List<Integer>>();
        List<Integer> curList=new ArrayList<>();
        Arrays.sort(arr);
        backTrackingUnduplicate(resList,curList,arr,target,0);
        return resList;
    }
    private boolean backTrackingUnduplicate(List<List<Integer>> resList,
            List<Integer> curList, int[] arr, int remain, int start) {

        if(remain==0){
            resList.add(new ArrayList<Integer>(curList));
            return false;
        }
        if(remain<0){
            return false;
        }
        else{
            for(int i=start;i<arr.length;i++){
                
                curList.add(arr[i]);
                boolean flag=backTrackingUnduplicate(resList, curList, arr, remain-arr[i], i+1);
                curList.remove(curList.size()-1);
                if(!flag){
                    break;
                }
            }
            return true;

        }
    }

數組中包含有重復的元素，且每個元素只能用一次。最后的結果中不含重復的結果集。
Combination Sum 2

Given a collection of candidate numbers (C) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.

Each number in C may only be used once in the combination.

Note:

All numbers (including target) will be positive integers.
The solution set must not contain duplicate combinations.

For example, given candidate set [10, 1, 2, 7, 6, 1, 5] and target 8,
A solution set is:

[
[1, 7],
[1, 2, 5],
[2, 6],
[1, 1, 6]
]

public List<List<Integer>>  getAllCombinationUnduplicate(int[] arr,int target){
        List<List<Integer>> resList=new ArrayList<List<Integer>>();
        List<Integer> curList=new ArrayList<>();
        Arrays.sort(arr);
        backTrackingUnduplicate(resList,curList,arr,target,0);
        return resList;
    }
    private boolean backTrackingUnduplicate(List<List<Integer>> resList,
            List<Integer> curList, int[] arr, int remain, int start) {

        if(remain==0){
            resList.add(new ArrayList<Integer>(curList));
            return false;
        }
        if(remain<0){
            return false;
        }
        else{
            for(int i=start;i<arr.length;i++){
                curList.add(arr[i]);
                boolean flag=backTrackingUnduplicate(resList, curList, arr, remain-arr[i], i+1);
                curList.remove(curList.size()-1);
                if(!flag){
                    break;
                }
                while(i<arr.length-1 && arr[i]==arr[i+1]){
                    i++;
                }
            }
            return true;

        }
    }

比如數組a={1,1,1,1,2}，target=4.用上面解法的過程見下圖：


image.png

Combination Sum 3

Find all possible combinations of k numbers that add up to a number n, given that only numbers from 1 to 9 can be used and each combination should be a unique set of numbers.

Example 1:

Input: k = 3, n = 7

Output:

[[1,2,4]]
Example 2:

Input: k = 3, n = 9

Output:

[[1,2,6], [1,3,5], [2,3,4]]

public List<List<Integer>>  getAllCombinationUnduplicate(int[] arr,int target,int k){
        List<List<Integer>> resList=new ArrayList<List<Integer>>();
        List<Integer> curList=new ArrayList<>();
        Arrays.sort(arr);
        int count=0;
        backTrackingUnduplicate(resList,curList,arr,target,0,k);
        return resList;
    }
    private boolean backTrackingUnduplicate(List<List<Integer>> resList,
            List<Integer> curList, int[] arr, int remain, int start,int k) {

        if(remain==0 && curList.size()==k){
            
            resList.add(new ArrayList<Integer>(curList));
            return false;
        }
        if(remain<0){
            return false;
        }
        else{
            for(int i=start;i<arr.length;i++){
                if(remain-arr[i]>0 && curList.size()+1==k ){
                    continue;
                }
                curList.add(arr[i]);
                boolean flag=backTrackingUnduplicate(resList, curList, arr, remain-arr[i], i+1,k);
                curList.remove(curList.size()-1);
                if(!flag){
                    break;
                }
                while(i<arr.length-1 && arr[i]==arr[i+1]){
                    i++;
                }
            }
            return true;

        }
    }

Combinations

Given two integers n and k, return all possible combinations of k numbers out of 1 ... n.

For example,
If n = 4 and k = 2, a solution is:

[
[2,4],
[3,4],
[2,3],
[1,2],
[1,3],
[1,4],
]

    public List<List<Integer>> getAllCombinations(int[] a,int k){
        List<List<Integer>> resList = new ArrayList<>();
        List<Integer> curList=new ArrayList<>();
        Arrays.sort(a);
        backTrack(resList, curList, a, 0,k);
        return resList;
    }
    /**
     * @param resList
     * @param curList
     * @param a
     * @param i
     *<p>Description: </p>  
     */
    private void backTrack(List<List<Integer>> resList,
            List<Integer> curList, int[] a, int start,int k) {
        if(curList.size()==k){
            resList.add(new ArrayList(curList));
            return;
        }
        
        for(int i=start;i<a.length;i++){
            curList.add(a[i]);
            backTrack(resList, curList, a, i+1, k);
            curList.remove(curList.size()-1);
        }
        //return;寫不寫的區(qū)別是啥
        
    }

Letter Combinations of a Phone Number

Given a digit string, return all possible letter combinations that the number could represent.

A mapping of digit to letters (just like on the telephone buttons) is given below.


image.png

Input:Digit string "23"
Output: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].

public List<String> getStringCombinaList(String input){
        List<String> resList=new ArrayList<>();
        StringBuilder sb=new StringBuilder();
        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");
        int start=0;
        backTrackHelper(resList,sb,input,map,start);
        return resList;
        
        
        
    }
    /**
     * @param resList
     * @param sb
     * @param input
     * @param map
     * @param start
     *<p>Description: </p>  
     */
    private void backTrackHelper(List<String> resList, StringBuilder sb,
            String input, Map<Character, String> map, int start) {

        if(sb.length()==input.length()){
            resList.add(sb.toString());
            return;
        }
        String temp=map.get(input.charAt(start));
        for(int i=0;i<temp.length();i++){
            sb.append(temp.charAt(i));
            backTrackHelper(resList, sb, input, map, start+1);
            sb.deleteCharAt(sb.length()-1);
        }
    }

Given a set of distinct integers, nums, return all possible subsets.

Note: The solution set must not contain duplicate subsets.

For example,
If nums = [1,2,3], a solution is:

[
[3],
[1],
[2],
[1,2,3],
[1,3],
[2,3],
[1,2],
[]
]
解法1：回溯

public List<List<Integer>> getAllSet(List list){
       List<List<Integer>> resList=new ArrayList();
       if(list.size()==0){
           return resList;
       }
       List curList=new ArrayList<>();
       backTrackSubset(resList,list,curList,0);
       return resList;
   }

   /**
    * @param resList
    * @param list
    * @param i
    *<p>Description: </p>  
    */
   private void backTrackSubset(List<List<Integer>> resList, List list,List curList, int current) {

       resList.add(new ArrayList(curList));
       
       for(int i=current;i<list.size();i++){
           curList.add(list.get(i));
           backTrackSubset(resList, list, curList, i+1);
           curList.remove(curList.size()-1);
       }
   }

解法2：動態(tài)規(guī)劃（有個問題沒有解決）
Java集合的拷貝構造函數只提供淺拷貝而不是深拷貝

public Set<Set<Integer>> getAllSubSetDyn(int[] a,int n){
        Set<Set<Integer>> resSet=new HashSet<>();
        if(n==0){
        resSet.add(new HashSet<>());
        return resSet;
        }
        Set<Set<Integer>> set=getAllSubSetDyn(a, n-1);
        for(Set<Integer> s:set){
            Set<Integer> setCopy=new HashSet<>(s);//集合默認是淺拷貝
            setCopy.add(a[n-1]);
            resSet.add(new HashSet<Integer>(setCopy));//    resSet.add(setCopy);

            resSet.add(new HashSet<Integer>(s));
        }
        return resSet;
    }

Subsets II (contains duplicates)

Given a collection of integers that might contain duplicates, nums, return all possible subsets.

Note: The solution set must not contain duplicate subsets.

For example,
If nums = [1,2,2], a solution is:

[
[2],
[1],
[1,2,2],
[2,2],
[1,2],
[]
]

public List<List<Integer>> getAllSetDuplicate(int[] a){
       List<List<Integer>> resList=new ArrayList<>();

       if(a.length<=0){
           return resList;
       }
       Arrays.sort(a);
       List curList=new ArrayList<>();
       backTrackSubsetDuplicate(resList,curList,a,0);
       return resList;
       
   }
   /**
    * @param resList
    * @param curList
    * @param a
    * @param i
    *<p>Description: </p>  
    */
   private void backTrackSubsetDuplicate(List<List<Integer>> resList,
           List curList, int[] a, int start) {

       resList.add(new ArrayList<>(curList));
       for(int i=start;i<a.length;i++){
           curList.add(a[i]);
           backTrackSubsetDuplicate(resList, curList, a, i+1);
           curList.remove(curList.size()-1);
           while(i<a.length-1 && a[i]==a[i+1]){
               i++;
           }
       }
   }

Given a collection of distinct numbers, return all possible permutations.

For example,
[1,2,3] have the following permutations:

[
[1,2,3],
[1,3,2],
[2,1,3],
[2,3,1],
[3,1,2],
[3,2,1]
]

public List<List<Integer>> getPermutations(int[] a){
        List<List<Integer>> resList=new ArrayList<>();
        if(a.length<=0){
            return resList;
        }
        
        List<Integer> curList=new ArrayList<>();
        backtrackPermutation(resList,curList,a);
        return resList;
    }
    /**
     * @param resList
     * @param curList
     * @param a
     *<p>Description: </p>  
     */
    private void backtrackPermutation(List<List<Integer>> resList,
            List<Integer> curList, int[] a) {

        if(curList.size()==a.length){
            resList.add(new ArrayList<>(curList));
        }
        
        for(int i=0;i<a.length;i++){
            if(curList.contains(a[i])){
                continue;
            }
            curList.add(a[i]);
            backtrackPermutation(resList, curList, a);
            curList.remove(curList.size()-1);
        }
    }

Given a collection of numbers that might contain duplicates, return all possible unique permutations.

For example,
[1,1,2] have the following unique permutations:

[
[1,1,2],
[1,2,1],
[2,1,1]
]

    
    public List<List<Integer>> getPermutationDuplicate(int a[]){
        List<List<Integer>> resList=new ArrayList<>();
        Arrays.sort(a);
        List<Integer> curList=new ArrayList<>();
        boolean[] flag=new boolean[a.length];
        backTrackPermutationDup(resList,curList,a,flag);
        return resList;
    }

    /**
     * @param resList
     * @param curList
     * @param a
     *<p>Description: </p>  
     */
    private void backTrackPermutationDup(List<List<Integer>> resList,
            List<Integer> curList, int[] a,boolean[] flag) {

        if(curList.size()==a.length){
            resList.add(new ArrayList<Integer>(curList));
        }
        
        
        for(int i=0;i<a.length;i++){
            if(flag[i]){
                continue;
            }
            
            curList.add(a[i]);
            flag[i]=true;
            
            backTrackPermutationDup(resList, curList, a, flag);
            curList.remove(curList.size()-1);
            flag[i]=false;
            while(i<a.length-1 && a[i]==a[i+1]){
                i++;
            }
        }
    }

Given a binary tree, return all root-to-leaf paths.

Note: A leaf is a node with no children.

Example:

Input:

1
/
2 3

5

Output: ["1->2->5", "1->3"]

Explanation: All root-to-leaf paths are: 1->2->5, 1->3

public List<String> getAllPaths(TreeNode root){
        List<String> list=new ArrayList<String>();
        if(root == null){
            return list;
        }
        StringBuilder sb=new StringBuilder();
        backTracking(root,list,sb);
        return list;
        
    }
    /**
     * @param root
     * @param list
     * @param sb
     *<p>Description: </p>  
     */
    private void backTracking(TreeNode root, List<String> list, StringBuilder sb) {

        if(root == null){
            return;
        }
        int length=sb.length();

        if(root.getLeft() == null && root.getRight() == null){
            sb.append(root.getValue());
            list.add(sb.toString());
        }
        else{
            sb.append(root.getValue());
            sb.append("->");
            backTracking(root.getLeft(), list, sb);
            backTracking(root.getRight(), list, sb);
        }
    
        sb.setLength(length);//截取
    }
最后編輯于 ：
?著作權歸作者所有,轉載或內容合作請聯(lián)系作者
【社區(qū)內容提示】社區(qū)部分內容疑似由AI輔助生成，瀏覽時請結合常識與多方信息審慎甄別。
平臺聲明：文章內容（如有圖片或視頻亦包括在內）由作者上傳并發(fā)布，文章內容僅代表作者本人觀點，簡書系信息發(fā)布平臺，僅提供信息存儲服務。

相關閱讀更多精彩內容

  • 背景 一年多以前我在知乎上答了有關LeetCode的問題, 分享了一些自己做題目的經驗。 張土汪：刷leetcod...
    土汪閱讀 12,916評論 0贊 33
  • iOS面試中熟悉常見算法 1、 對以下一組數據進行降序排序（冒泡排序）?！?4，17，85，13，9，54，76，...
    修一辰閱讀 475評論 0贊 0
  • 通信原理（學習筆記） 第二章 信道 第3講 信道的概念和實際信道 信道的定義信道：信號傳輸的通道信號處理的角度：信...
    快樂的大腳aaa閱讀 1,259評論 0贊 0
  • 今天主要學了如何利用windows操作系統(tǒng)的漏洞進行后門提權。主要用到的工具有nessus、metasploit、...
    kotw_zjc閱讀 1,593評論 0贊 0
  • 1、lvs-tun模式 轉發(fā)方式：不修改請求報文的IP首部（源IP為CIP，目標IP為VIP），而在原IP報文之外...
    阿喪小威閱讀 254評論 0贊 0

友情鏈接更多精彩內容