[关闭]
@xmruibi 2015-03-03T00:00:25.000000Z 字数 9591 阅读 887

Backtracking Summary -- Permutation&Combiniation Problems

Algorithm

Backtracking Summary -- Permutation&Combiniation Problems:

0. Preface:

回溯法的是来解决多维向量的枚举问题，其核心:
- 递归的枚举每个维度的值
- 既然是递归，那就用终止条件。一般的终止条件是找到了满足条件的解，或者已经超出了解的范围，无需再递归下去。
- 找到某一维的候选值。解排列组合的重中之重。常用的技巧是使用标志位来记录某一维是否可用。
- make_move和unmake_move在对每个候选值递归调用前后发生，这里的unmake_move非常的重要，保证了回溯法的正确！

    Refenrece: http://www.csie.ntnu.edu.tw/~u91029/Backtracking.html

  1.         backtrack( [v1,...,vn] )    // [v1,...,vn] multi-dimension array
  2.         {
  3.             /* generated one set of multi-dimension array */
  4.                 if ( solution[] is well-generated )
  5.                 {
  6.                     check and record solution;
  7.                     return;
  8.                 }
  10.             /* 窮舉這個維度的所有數值，並遞迴到下一個維度 */
  11.                 for ( x = each value of current dimension )
  12.                 {
  13.                     solution[dimension] = x;
  14.                     backtrack( dimension + 1 );
  15.                 }
  16.         }
  18.         main: call backtrack( [] );   // 從第一個維度開始依序枚舉

1. Permutation Problem:

    1.Permutations
    2.Permutations II
    3.Next Permutation
    4.Permutation Sequence

1.1 Permutations:

  1.      Boolean isUsed;
  2.      public List<List<Integer>> permute(int[] num) {
  3.         isUsed = new Boolean[num.length];
  4.         List<List<Integer>> result = new ArrayList<List<Integer>>();
  5.         helper(0,num,new ArrayList<Integer>(),result);
  6.         return result;
  7.      }
  9.      private void helper(int start, int[] num, List<Integer> curList,List<List<Integer>> result){
  10.         if(start == num.length){
  11.             result.add(new ArrayList<Integer>(curList));
  12.             return;
  13.         }
  15.         for(int i=0;i<num.length;i++){
  16.             if(!isUsed[i]){
  17.                 curList.add(num[i]);
  18.                 isUsed[i] = true;
  19.                 helper(start+1,num,curList); //start 
  20.                 isUsed[i] = false;
  21.                 curList.remove(start);
  22.                 }
  23.         }
  24.      }

1.2 Permutation2

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

想要避免產生重複排列，在枚舉某一個位置的字母時，避免重複填入一樣的字母。
若將輸入的字串由小到大排序，字母會依照順序出現，所以只需檢查方上一个字母，判斷一不一樣，就可以避免填入一樣的字母了。

  1.      Boolean isUsed;
  2.      public List<List<Integer>> permute(int[] num) {
  3.         isUsed = new Boolean[num.length];
  4.         List<List<Integer>> result = new ArrayList<List<Integer>>();
  5.         Array.sort(num); //!!!!  
  7.         helper(0,num,new ArrayList<Integer>(),result);
  8.         return result;
  9.      }
  11.      private void helper(int start, int[] num, List<Integer> curList,List<List<Integer>> result){
  12.         if(start == num.length){
  13.             result.add(new ArrayList<Integer>(curList));
  14.             return;
  15.         }
  17.         for(int i=0;i<num.length;i++){
  19.         // Notice this!! avoid senarios like: abb, abb;
  20.             if (i>0&&num[i]==num[i-1]&&(!isUsed[i-1]))
  21.                 continue;
  23.             if(!isUsed[i]){
  24.                 curList.add(num[i]);
  25.                 isUsed[i] = true;
  26.                 helper(start+1,num,curList); //start 
  27.                 isUsed[i] = false;
  28.                 curList.remove(start);
  29.                 }
  30.         }
  31.      }

1.3 Next Permutation:

1). Lexicographical order
 - Step1：从最右开始，找到第一个比右边小的数字4（因为4<7, 而7>5>2>1），再从最右开始，找到4右边比4大的数字5（因为4>2>1而4<5）。4、5也即从右往左找到的第一个对严格的升序对。
 - Step2：交换4、5。
 - Step3：倒置5右边的7421为1247.即得到下一个排列839651247.

  1.     private static void LexicographicalOrder(int[] num) {
  2.         //从最右开始，找到第一个比右边小的数字num[minFromRight]
  3.             int minFromRight=-1;
  4.             for(int i=num.length-1;i>0;i--){
  5.                 if(num[i]>num[i-1]){
  6.                     minFromRight = i-1;
  7.                     break;
  8.                 }
  9.             }
  10.         // 再从最右开始，找到num[minFromRight]右边比它大的数字并交换
  11.             if(minFromRight>=0)
  12.                 for(int i=num.length-1;i>minFromRight;i--){
  13.                     if(num[i]>num[minFromRight]){
  14.                         int tmp = num[i];
  15.                         num[i]=num[minFromRight];
  16.                         num[minFromRight] = tmp;
  17.                         minFromRight++;
  18.                         break;
  19.                     }                       
  20.                 }
  21.             else
  22.                 minFromRight++;
  23.             // 从minFromRight 位置以后的数做倒序处理
  24.             reverseNum(num, minFromRight);
  26.     }
  28.     private static void reverseNum(int[] num, int index) {
  29.         // TODO Auto-generated method stub
  30.         int end = num.length-1;     
  31.         while(index<end){
  32.             int tmp = num[index];
  33.             num[index] = num[end];
  34.             num[end] = tmp;
  35.             index++;
  36.             end--;
  37.         }   
  38.     }

1.4 Permutation Sequence:

  1.         public String getPermutation(int n, int k) {
  2.               StringBuilder sb = new StringBuilder();         
  3.               int[] fact = new int[n];  // saving the factorial
  5.               // prepare the factorials
  6.               for (int i=1; i<=n; ++i) {  
  7.                      sb.append(i);  
  8.                      if (i == 1)  
  9.                        fact[i-1] = 1;  
  10.                      else  
  11.                        fact[i-1] = fact[i-2] * i;  
  12.                    }  
  14.               // make sure k is inside the sequence
  15.               k = k%fact[n-1];
  16.               k--;
  18.               for(int i=0;i<n;i++){
  19.                   int id = k/fact[(n-1)-1-i]+i; // +i!!??
  20.                   // get target number
  21.                   char num = sb.charAt(id);
  23.                   // shift number
  24.                   for(int j=id;j>i;j--)
  25.                       sb.setCharAt(j, sb.charAt(j--));
  27.                   sb.setCharAt(i, num);
  28.                   k=k%fact[(n-1)-1-i];
  29.               }
  31.               return sb.toString();
  32.         }

2. Combination& Subsets

    Subsets
    Subsets II
    Combinations
    Combination Sum
    Combination Sum II

2.1 Subset I:

  1.     // METHOD ONE:
  2.     public static void subset(int[] num,int index) {
  3.         if(index == num.length-1){
  4.             for(int i=0;i<num.length;i++){
  5.                 if(table[i])
  6.                     System.out.print(num[i]+" ");
  7.             }
  9.             System.out.println("");
  10.             return;
  11.         }
  13.         table[index] = true;
  14.         subset(num, index+1);
  16.         table[index] = false;
  17.         subset(num, index+1);
  18.     }
  20.     // METHOD TWO:
  21.     private static void subset2(int[] num,int index, int size) {
  22.         // TODO Auto-generated method stub
  23.         if(index == num.length-1){
  24.             for(int i=0;i<size;i++){
  25.                     System.out.print(num[i]+" ");
  26.             }
  28.             System.out.println("");
  29.             return;
  30.         }
  32.         num[size] = index;
  33.         subset2(num,index+1,size+1);
  35.         subset2(num,index+1,size);
  36.     }
  39.     另有二进制转化法， 请查阅 [Bit  Operation][https://www.zybuluo.com/xmruibi/note/71723] 章节即将每个组合与一个二进制数对应起来，枚举二进制的同时，枚举每个组合。这种方法由于有一一对应的特质，所以要求原数组中的各元素应该各不相同，否则求出来的子集和会有重复元素。

2.2 Subset II:

  1.     public static List<List<Integer>> subsetsWithDup(int[] num) {
  2.         List<List<Integer>> result = new ArrayList<List<Integer>>();
  3.         List<Integer> subset = new ArrayList<Integer>();
  4.         Arrays.sort(num);
  6.         subsetwDuphelper(num, 0, subset, result);
  7.         return result;
  8.     }
  10.     private static void subsetwDuphelper(int[] num, int start,
  11.             List<Integer> subset, List<List<Integer>> result) {
  13.         result.add(new ArrayList<>(subset));
  15.         for (int i = start; i < num.length; i++) {
  16.             // 注意此处 i!=start
  17.             if (i !=start && num[i] == num[i - 1])
  18.                 continue;
  19.             subset.add(num[i]);
  20.             subsetwDuphelper(num, i + 1, subset, result);
  21.             subset.remove(subset.size() - 1);
  22.         }
  23.     }

2.3 Combinations

  1.     //METHOD ONE:
  2.     public List<List<Integer>> combine(int n, int k){
  3.         List<List<Integer>> result = new ArrayList<List<Integer>>();
  4.         combine(n, k, 1, result, new ArrayList<Integer>());
  5.         return result;
  6.     }
  8.     public void combine(int n, int k , int start, List<List<Integer>> result, ArrayList<Integer> list){
  9.         // stop point
  10.         if(k==0){
  11.             result.add(list);
  12.             return;
  13.         }
  15.         for(int i= start;i<=n;i++){
  16.             ArrayList<Integer> curlist = (ArrayList<Integer>)list.clone();
  17.             curList.add(i);
  18.             combine(n,k-1,i+1,result,curlist);
  19.         }
  21.     }

2.4 Combination Sum I

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

  1.     public List<List<Integer>> combinationSum2(int[] num, int target) {  
  2.         List<List<Integer>> res = new ArrayList<List<Integer>>();  
  3.         int m = num.length;  
  4.         if(m == 0) return  res;  
  5.         Arrays.sort(num);  
  6.         List<Integer> item = new ArrayList<Integer>();  
  7.         helper(num, 0, target, item, res);  
  8.         return res;  
  9.     }
  11.     private void helper(int[] num, int start, int target, ArrayList<Integer> list, ArrayList<ArrayList<Integer>> result){
  12.         if(target == 0){
  13.             result.add(list);
  14.             return;
  15.         }
  17.         for(int i=start;i<num.length;i++){
  18.             if(i>0&&num[i]==num[i-1])
  19.                 continue;
  20.             list.add(num[i]);
  21.             helper(num,i,target-num[i],list, result); 
  22.             list.remove(i);
  23.         }
  24.     }

2.5 Combination Sum II

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

  1.     public List<List<Integer>> combinationSum2(int[] num, int target) {  
  2.         //1240  
  3.         List<List<Integer>> res = new ArrayList<List<Integer>>();  
  4.         int m = num.length;  
  5.         if(m == 0) return  res;  
  6.         Arrays.sort(num);  
  7.         List<Integer> item = new ArrayList<Integer>();  
  8.         dfs(num, target, 0, item, res);  
  9.         return res;  
  10.     }  
  12.     public void dfs(int[] num, int target, int start, List<Integer> item, List<List<Integer>> res){  
  13.         if(target == 0){  
  14.             res.add(new ArrayList<Integer>(item));  
  15.             return;  
  16.         }  
  17.         if(target < 0) return;  
  18.         for(int i = start; i < num.length; i++){  
  19.             if(i > start && num[i] == num[i-1]) continue;// avoid duplicate solutions  
  20.             item.add(num[i]);  
  21.             dfs(num, target - num[i], i + 1, item, res);  
  22.             item.remove(item.size() - 1);  
  23.         }  
  24.     }

3 Applications based on above problem

3.1 Letter Combination on Phone

  1. public List<String> letterCombinations(String digits) {
  3.         List<String> combList = new ArrayList<String>();
  4.         combList.add("");
  5.         for (int i = 0; i < digits.length(); i++) {
  6.             List<String> subList = new ArrayList<String>();
  7.             String letter = getLetters(digits.charAt(i));
  8.             for(int j=0;j<combList.size();j++){ // get previous list element then add letter on them
  9.                 for(int k = 0;k<letter.length();k++){
  10.                     subList.add(combList.get(j)+letter.charAt(k));
  11.                 }
  12.             }
  13.             combList = subList;
  14.         }
  15.         return combList;
  16.     }
  18.     private String getLetters(char digit) {
  19.         switch (digit) {
  20.         case '2':
  21.             return "abc";
  22.         case '3':
  23.             return "def";
  24.         case '4':
  25.             return "ghi";
  26.         case '5':
  27.             return "jkl";
  28.         case '6':
  29.             return "mno";
  30.         case '7':
  31.             return "pqrs";
  32.         case '8':
  33.             return "tuv";
  34.         case '9':
  35.             return "wxyz";
  36.         case '0':
  37.             return " ";
  38.         default:
  39.             return "";
  40.         }
  41.     }

3.2 Restore IP Address:

  1. public List<String> restoreIpAddresses(String s) {
  2.         List<String> res = new ArrayList<String>();
  3.         if(s==null || s.length()==0||s.length()>12)  
  4.             return res; 
  5.         helper(0, 1, "", s, res);
  7.         return res;
  8.     }
  9.     // separated into 4 segments
  10.     private void helper(int index, int segment, String cur, String addr,
  11.             List<String> res) {
  12.            if(index>=addr.length())  
  13.                 return;
  14.         if(segment == 4){
  15.             String str = addr.substring(index,addr.length());
  16.             if(isValid(str)){
  17.                 res.add(cur+"."+str);
  18.                 return;
  19.             }
  20.         }
  22.         for (int i = 1; i < 4 && (i + index <= addr.length()); i++) {
  23.             String str = addr.substring(index, index + i);
  24.             if (isValid(str)) {
  25.                 if (segment == 1) {
  26.                     helper(index + i, segment + 1, str, addr, res);
  27.                 } else {
  28.                     helper(index + i, segment + 1, cur +"."+ str, addr, res);
  29.                 }
  30.             }
  31.         }
  32.     }
  34.     private boolean isValid(String str) {
  35.         if (str == null || str.length() > 3)
  36.             return false;
  37.         if (str.charAt(0) == '0' && str.length() > 1)
  38.             return false;
  39.         if (Integer.parseInt(str) <= 255 && Integer.parseInt(str) >= 0)
  40.             return true;
  42.         return false;
  43.     }

3.3 Generate Parenthese

  1.     public static List<String> generateParenthesis(int n) {
  2.         List<String> list = new ArrayList<String>();
  3.         generate(n, 0, "", list);
  4.         return list;
  5.     }
  7.     /**
  8.      * 
  9.      * @param fpNum the number of "("
  10.      * @param bpNum the number of ")"
  11.      * @param product current product
  12.      * @param list
  13.      */
  14.     private static void generate(int fpNum, int bpNum, String product,
  15.             List<String> list) {
  16.         // TODO Auto-generated method stub
  17.         if (fpNum == 0 && bpNum == 0) {
  18.             list.add(product);
  19.             return;
  20.         }
  22.         if (fpNum > 0) {
  23.             generate(fpNum - 1, bpNum + 1, product + "(", list);
  24.         }
  25.         if (bpNum > 0) {
  26.             generate(fpNum, bpNum - 1, product + ")", list);
  27.         }
  28.     }

2.4 Palindrome Partitioning

Given a string s, partition s such that every substring of the partition is a palindrome.
Return all possible palindrome partitioning of s.

  1.     public static List<List<String>> partition(String s) {
  2.         List<List<String>> res = new ArrayList<List<String>>();
  3.         backTrack(s, 0, new ArrayList<String>(), res);
  4.         return res;
  5.     }
  7.     private static void backTrack(String s, int start,
  8.             ArrayList<String> curlist, List<List<String>> res) {
  9.         // TODO Auto-generated method stub
  10.         if (curlist.size() > 0 && start == s.length()) {
  11.             res.add(new ArrayList<String>(curlist));
  12.             return;
  13.         }
  15.         for (int i = start + 1; i <= s.length(); i++) {
  16.             String str = s.substring(start, i);
  17.             if (isPalindrome(str)) {
  18.                 curlist.add(str);
  19.                 backTrack(s, i, curlist, res);
  20.                 curlist.remove(curlist.size() - 1);
  21.             }
  22.         }
  23.     }
  25.     private static boolean isPalindrome(String str) {
  26.         int l = 0;
  27.         int r = str.length() - 1;
  28.         while (l < r) {
  29.             if (str.charAt(l) != str.charAt(r))
  30.                 return false;
  31.             l++;
  32.             r--;
  33.         }
  34.         return true;
  35.     }
添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注