LeetCode Summary(2) -- Permutation and Combination

Permutation and Combination 题目很多, 算是基本题型，幸好大部分程序的框架都很类似，根据题目修改一些条件判断就可以了，答案需要统一化，这类题目没有任何理由不bug free，理解了之后 逻辑应该非常清晰，代码难度也不大.
这类题目实质就是DFS + BackTracking. 对于这两种思想的理解非常有帮助.


基本的Permutation & Combination 题目 7 道

• Permutation
• Permutation II 
• Subset
• Subset II
• Combination
• CombinationSum 
• CombinationSum II

应用场景题目9道

• Letter Combination of PhoneNumber
• Palindrome Partitioning
• Restore IP Address
• Path Sum II
• Sum Root to Leaf
• N-Queens I
• N-Queens II
• Work Break II
• Substring with Concatenation of All Words

Combination Sum Codes

     public ArrayList<ArrayList<Integer>> combinationSum(int[] candidates, int target) {  
         Arrays.sort(candidates);  
         ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();  
         ArrayList<Integer> list = new ArrayList<Integer>();  
   
         combinationSumHelper(result, list, candidates, target, 0);  
         return result;  
     }  
   
     private void combinationSumHelper(ArrayList<ArrayList<Integer>> result,   
             ArrayList<Integer> list, int[] candidates, int target, int position) {  
           
         int sum = 0;  
         for (int x: list) {  
             sum += x;   
         }  
           
         if (sum == target) {  
             result.add(new ArrayList<Integer>(list));  
             return;  
         }  
   
         if (sum < target) {  
             for (int i = position; i < candidates.length; i++) {  
                 list.add(candidates[i]);  
                 combinationSumHelper(result, list, candidates, target, i);  
                 list.remove(list.size() - 1);  
             }  
         }  
     }  

程序注意事项.

考虑

• 满足的条件使result.add(new ArrayList<E>(list)), 一定new 新的，否则添加list的引用无效
• for loop 中，有哪些element需要跳过，
• 递归的的条件是什么，传入i or i+1 等等， 这里编程注意，我老写着就写成position + 1了 

特性: 

1. Subset,  Combination, Combination Sum 的每道题目都要求 non - descending order，所以一定是要先Arrays.sort(S) 一下.  递归过程中要保证所取元素升序，需要position 来标记起始位， Permutation 不用，每次都从0开始

2. Permutation, Subset, Combination Sum. 都有duplicate 的follow up 题目, 面试很可能会连着问

1. Permutation
添加条件，list.size() == num.length. 够了才添加，每次取值都是从0开始取, 所以不需要position，i start from 0, 另外不允许重复出现，所以 list.contains(num[i]) 要continue

2. Permutation II 
多了duplicate的条件，之前的list.contains(num[i]) 显然不能用了，需要 boolean[] visited 来标记每个节点是否访问过，如果duplicate元素，第二个在第一个没用之前，不能用, 跳过的条件是，
visited[i] == true || (i != 0 && num[i] == num[i - 1] && visited[i - 1] == false)

3. Subset
和combination，permutation不同的是，添加到result的条件没有了，此时也不能return，subset必须用升序，来保证subset的唯一，所以先排序，每次添加的数字一定是大于第一个数字，递归时候需要 i+1. 

4. Subset II
多了duplicates的条件，和permutation II 差不多，需要skip掉 i != position && num[i] == num[i - 1]的element, 添加时候每次都是 i = position. 不用管duplicate，主要是回溯过程中，要考虑重复值的问题.

5. Combination
没什么特别，input 给的是n，记得从 1开始就好，别写成0了。

6. CombinationSum 
可以重复加一个element，所以每次递归，传入i，下次还从 candidate[i] 上取

7. CombinationSum II

每个element只能使用1次，迭代条件是 i + 1， 
同时多了duplicate的条件,  跟subset II 一样，skip掉 i != position && num[i] == num[i - 1].


场景题目

1. Letter Combination of PhoneNumber

一定要用递归思想，每次都是不同的group里选值, 所以每次调用的group都不同，建立 digits，每次调用的index， char[][] 的对应关系

index = Character.getNumericValue(digits.charAt(sb.length())); ---> 映射到 char[index] 

2. Palindrome Partitioning
很多分字符串的题目都是 combination 的，还有切割问题

这题非常考验对backtracking的理解，先分 prefix = str.substring(position, i +1)
新切割的时候， i = position，回溯的时候，i++，也就是interval变成2，3…回溯的过程中让interval 变大，这样可以控制所有的切割，只要判断prefix isPanlindrome即可，当切割到最后一位，position == s.length() 保存结果 
[a, a, b, b, a, a] --> [a, a, b, b, aa] -> [a,a, bb, a,a] --> [a, a, bb, aa]

3. Restore IP Address
IP 每个段得判断，得用long 防止12位的int溢出， 要判断 string 开头为0，length != 1的case
终止条件  list.size() == 4 && position == s.length() 跟Palindrome Partition 这个题目差不多，就是条件的变化

4. Path Sum II
主要是终止条件的判断, 对于一般节点，3种情况
1. root.left == null || root.right == null.  sum == 0  return  只有这种我们添加 到result
2. root.left == null || root.right == null.  sum != 0  return
3. root left, right 有一个不为空，不为空得递归到1.2 两种情况，另一种递归到 root == null. return. 
树跟int[] 没什么不同, 只是算完left，回溯到parent, 再算一遍右边.
helper(result, list, root.left, sum);  --> helper(result, list, root.right, sum)

5. Sum Root to Leaf
跟Path Sum II 基本一样，但是条件不能简单的归结为root == null 时候return，sum += value. 
因为这样的话，left，right 会各计算一次，还是按照path sum II的结构写

6. N-Queens I
本质是个排列问题，因为Queen的位置不一定是升序的，所以不需要position来标记。
skip的地方，需要查看isValid(cols, col) , 也就是插入 这个 col，原来的cols能不能valid, 不能就continue，
剩下的都是编程问题

7. N-Queens II
为了简便，写的和N-Queen一模一样，省掉了drawChessBoard. 返回result的size即可

8. Work Break II
这道题目直接用类似 Palindrome Partitioning的方式, 会Time Limit Exceeded, 原因是中间切割的过程有大量的重复计算，需要一个一维的数组来标记 (i+1, n-1) 有没有结果，DP问题。

9. Substring with Concatenation of All Words

还在超时中，没搞定