算法小结 -- barktracking & dfs

Back Tracking(a form of recursion)
 https://www.cis.upenn.edu/~matuszek/cit594-2012/Pages/backtracking.html
The idea of back tracking:

 It's like going into a maze, and do a silly exhausted depth first search. At when you at one point you have a set of opitions to go. When you meet the dead end, you need to go back to the last successful decision point, and try another direction.(for remove part)

for loop 里面 call recursive function
下面橙色划出的为固定步骤, 有for loop是因为不同order matter，不然不需要。

public void dfs(int[] candidates, int target,int target,int index, List<Integer> path,List<List<Integer>> res){    
  if(sum==target //base case){
            res.add(new ArrayList(path));
        }else if(sum >target){
            return;
        }
        for(int i=index;i<candidates.length;i++){//combination & subset 都是从下一个ele继续，permu是从0, for loop是代表当前点可以有的option,没用for loop是因为没有太多选择，所以没必要
            path.add(candidates[i]);
            sum += candidates[i];
            dfs(i,candidates,sum,target,path,res);// if allow repeats of current ele: i, if move forward: i+1
            sum -= path.get(path.size()-1);
            path.remove(path.size()-1);
       }
}
*进阶(dfs相似return情况)
» 207.201. Course Schedule I/II (DFS with adjacent list, topo) 各大家
http://rainykat.blogspot.com.tr/2017/01/leetcode-207-course-schedule-dfs-with.html 
» 211. Add and Search Word - Data structure design (Trie+ Backtracking) F家
http://rainykat.blogspot.com/2017/01/leetcodef-211-add-and-search-word-data.html


*Matrix,上下左右dfs
»  200. Number of Islands 各大家
http://rainykat.blogspot.com/2017/01/leetcode-200-number-of-islandsback.html 
»  286. Walls and Gates F家 G家
http://rainykat.blogspot.com/2017/01/leetcodegf-286-walls-and-gates.html 
»  79. Word Search F家微软
http://rainykat.blogspot.com/2017/01/leetcodef-79-word-search-backtracking.html

*Matrix, iterate by row, no return case
» 547. Find Friend Cycles
http://rainykat.blogspot.com/2017/04/leetcode-547-friend-circlesdfs.html

*单loop String 套路代码  -- few option at each char, no need use for loop

public void DFS(List<String> res, StringBuilder sb, char[] c, int i, int num) {
        int len = sb.length();// base case for return(depends)
        if(i==c.length){
            if(num>0)sb.append(num);
            res.add(sb.toString());
        }else{
            DFS(res,sb,c,i+1,num+1);//choice 1: not use
            if(num>0)sb.append(num);//choice 2: use & append
            DFS(res,sb.append(c[i]),c,i+1,0);
        }
        sb.setLength(len);//for all cases,since append sth(else duplicated char)
    }

 
» 22. Generate Parentheses G家UberZenefits
http://rainykat.blogspot.com/2017/02/leetcode-22-generate.html 
» 494. Target Sum G家F家
http://rainykat.blogspot.com/2017/01/leetcodegf-494-target-sum-dfs.html 
» 282. Expression Add Operators G家F家
http://rainykat.blogspot.com/2017/01/leetcodegf-282-expression-add.html 
» 320. Generalized Abbreviation G家
http://rainykat.blogspot.com/2017/01/leetcodeg-320-generalized.html
» 301. Remove Invalid Parenthesis F家
http://rainykat.blogspot.com/2017/01/leetcodef-301-remove-invalid-parentheses.html

---

» 17. Letter Combinations of a Phone Number (bakctracking)各大家
 注意dfs for loop

for(char c:map.get(digits.charAt(sb.length()))){//char index is sb length,c is ele is map list

http://rainykat.blogspot.com/2017/01/leetcode-17-letter-combinations-of.html 


» 39. Combination Sum Uber,Snapchat,
sort array 1st, watch return case, once target<0 no possible path
Complexity: Time O(n!) Space O(n) 
https://leetcode.com/problems/combination-sum/

public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> res = new ArrayList<>();
        Arrays.sort(candidates);
        dfs(candidates, res, target, new ArrayList<Integer>(), 0);
        return res;
    }
    void dfs(int[] candidates, List<List<Integer>> res, int target, List<Integer> path, int index){
        if(target == 0) res.add(new ArrayList(path));
        if(target <= 0) return;
        for(int i = index; i < candidates.length; i++){
            path.add(candidates[i]);
            dfs(candidates, res, target - candidates[i], path, i);
            path.remove(path.size() - 1);
        }
    }

» 40. Combination Sum II SnapChat
key is when skipping duplicate, we check condition that  i > index
eg 1,1,1,2,.. so we skip 3rd1 at index=1
Complexity: Time O(n!) Space O(n)
https://leetcode.com/problems/combination-sum-ii/

void dfs(int[] candidates, List<List<Integer>> res, int target, List<Integer> path, int index){
        if(target == 0) res.add(new ArrayList(path));
        if(target <= 0) return;
        for(int i = index; i < candidates.length; i++){
            if(i > index && candidates[i-1] == candidates[i])continue;
            path.add(candidates[i]);
            dfs(candidates, res, target - candidates[i], path, i+1);
            path.remove(path.size() - 1);
        }
    }

» 216. Combination Sum III
http://rainykat.blogspot.com/2017/02/leetcode-216-combination-sum-iii.html

» 78. Subsets I / 90. Subsets II F家，亚麻家
有duplicate的情况需要sort array 
详解： http://rainykat.blogspot.com/2017/01/leetcodef-78-subsets-i90ii-back-tracking.html
Subsets ||

public class Solution {
    public List<List<Integer>> subsetsWithDup(int[] nums) {
      List<List<Integer>> res = new  ArrayList<List<Integer>>();
      if(nums.length == 0){
        return res;
      }
      Arrays.sort(nums);
      dfs(nums, 0, new ArrayList<Integer>(), res);
      return res;
    }
    
    private void dfs(int[] nums,int index,List<Integer> path,List<List<Integer>> res){
        res.add(new ArrayList<Integer>(path));
    
        for(int i = index; i < nums.length; i++){
            if(i>index&&nums[i]==nums[i-1])continue;//to skip dupliacte number in array
            path.add(nums[i]);
            dfs(nums,i+1,path,res);
            path.remove(path.size()-1);
        }
    }
}

---

» 46. permutation LinkedIn 微软
https://leetcode.com/problems/permutations/
Time Complexity: O(n*n!) Note that there are n! permutations and it requires O(n) time to print a a permutation.
思路： Key is to keep a used[i] array, mark the element already added. So we skip such ele in dfs
            (can also be done through list.contains(i))

public class Solution {
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> res = new ArrayList<List<Integer>>();
        boolean[] used = new boolean[nums.length];//track if the digit already used
        dfs(res,new ArrayList<Integer>(),nums,used,0);
        return res;
    }
    public void dfs(List<List<Integer>> res,List<Integer> path,int[] nums,boolean[] used,int level){
        if(level==nums.length){
            res.add(new ArrayList(path));
            return;
        }
        for(int i=0;i<nums.length;i++){
            if(used[i])continue;//skip added element, eg: 123,back to point 1(added) 2(added) skip, then add 3, get123
            path.add(nums[i]);//i element placed in current recursion level = path.length,写着便于理解
            used[i] = true;//marked used
            dfs(res,path,nums,used,level+1);
            path.remove(path.size()-1);//return to last decision point
            used[i] = false;
        }
    }
}

» 47. permutation II LinkedIn 微软
多一个skip repeated path by sort array的步骤
http://rainykat.blogspot.com/2017/01/leetcodelinkedin-47-permutations.html 

---

» 77. combination c(n,k)
Complexity:　O(C(n,k)*k) which is O(n choose k)result each cost O(k) to copy list to res
https://leetcode.com/problems/combinations/

private void dfs(int n,int index,int k,List<Integer> path,List<List<Integer>> res){
        if(path.size()==k){
            res.add(new ArrayList(path));
        }
        for(int i = index;i<=n;i++){//i start from 1
            path.add(i);
            dfs(n,i+1,k,path,res);
            path.remove(path.size()-1);
        }
    }