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.

For example, given s = "aab",
Return

  [

    ["aa","b"],

    ["a","a","b"]

  ]

DFS，时间分析，一个有n-1的地方可以断开，所以有断和不断两种情况，所有情况就是2^n。 

public class Solution {
    //Time: O(2^n)
    public ArrayList<ArrayList<String>> partition(String s) {
        ArrayList<ArrayList<String>> res = new ArrayList<ArrayList<String>>();
        ArrayList<String> tmp = new ArrayList<String>();
        help(res, tmp, s, 0);
        return res;
    }
    
    private void help(ArrayList<ArrayList<String>> res, ArrayList<String> tmp, 
                      String s, int index) {
        if (index == s.length()) {
            res.add(new ArrayList<String>(tmp));
            return;
        }
        
        for (int i = index + 1; i <= s.length(); i++) {
            String cur = s.substring(index, i);
            if (valid(cur)) {
                tmp.add(cur);
                help(res, tmp, s, i);
                tmp.remove(tmp.size() - 1);
            }
        }
    }
    
    private boolean valid(String s) {
        int left = 0;
        int right = s.length() - 1;
        while (left < right) {
            if (s.charAt(left) != s.charAt(right)) {
                return false;
            }
            left++;
            right--;
        }
        return true;
    }
}

Letter Combinations of a Phone Number

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

Input:Digit string "23"

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

Note:
Although the above answer is in lexicographical order, your answer could be in any order you want.

用一个HashMap存好对应关系，然后DFS。

public class Solution {
    public ArrayList<String> letterCombinations(String digits) {
        ArrayList<String> res = new ArrayList<String>();
        HashMap<Integer, char[]> map = new HashMap<Integer, char[]>();
        map.put(0, new char[]{});
        map.put(1, new char[]{});
        map.put(2, new char[]{'a','b','c'});
        map.put(3, new char[]{'d','e','f'});
        map.put(4, new char[]{'g','h','i'});
        map.put(5, new char[]{'j','k','l'});
        map.put(6, new char[]{'m','n','o'});
        map.put(7, new char[]{'p','q','r','s'});
        map.put(8, new char[]{'t','u','v'});
        map.put(9, new char[]{'w','x','y','z'});
        combination(digits, map, res, 0, "");
        return res;
    }
    
    private void combination(String digits, HashMap<Integer, char[]> map,
                             ArrayList<String> res, int index, String s) {
        if (index == digits.length()) {
            res.add(s);
            return;
        }          
        
        char[] candidate = map.get(digits.charAt(index) - '0');
        for (int i = 0; i < candidate.length; i++) {
            combination(digits, map, res, index + 1, s + candidate[i]);
        }
    }
}

Combination Sum

Given a set of candidate numbers (C) 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.
• Elements in a combination (a1, a2, … , ak) must be in non-descending order. (ie, a1 ≤ a2 ≤ … ≤ ak).
• The solution set must not contain duplicate combinations.

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

DFS: 

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

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.
• Elements in a combination (a1, a2, … , ak) must be in non-descending order. (ie, a1 ≤ a2 ≤ … ≤ ak).
• 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] 

基本思路和permutation2一样，需要一个boolean array来帮助检测重复情况。

public class Solution {
    //Time: O(n^n)  
    public ArrayList<ArrayList<Integer>> combinationSum2(int[] num, int target) {
        ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
        ArrayList<Integer> tmp = new ArrayList<Integer>();
        Arrays.sort(num);
        boolean[] visit = new boolean[num.length];
        combination(res, tmp, num, visit, target, 0);
        return res;
    }
    
    private void combination(ArrayList<ArrayList<Integer>> res, ArrayList<Integer> tmp,
                             int[] num, boolean[] visit, int target, int index) {
        if (target < 0) {
            return;
        }  
        
        if (target == 0) {
            res.add(new ArrayList<Integer>(tmp));
            return;
        }
        
        for (int i = index; i < num.length; i++) {
            if (i != 0 && num[i] == num[i - 1] && !visit[i - 1]) {
                continue;
            }
            
            tmp.add(num[i]);
            visit[i] = true;
            combination(res, tmp, num, visit, target - num[i], i + 1);
            tmp.remove(tmp.size() - 1);
            visit[i] = false;
        }
    }
}

Subsets

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

Note:

• Elements in a subset must be in non-descending order.
• The solution set must not contain duplicate subsets.

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

[

  [3],

  [1],

  [2],

  [1,2,3],

  [1,3],

  [2,3],

  [1,2],

  []

]

就是一个DFS的过程，需要一个额外的index变量。注意这道题我们需要先sort下数组，这样才能保证升序。

public class Solution {
    //Time: O(n^n)
    public ArrayList<ArrayList<Integer>> subsets(int[] S) {
        ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
        ArrayList<Integer> tmp = new ArrayList<Integer>();
        Arrays.sort(S);
        subsetHelp(res, tmp, S, 0);
        return res;
    }
    
    private void subsetHelp(ArrayList<ArrayList<Integer>> res, ArrayList<Integer> tmp, 
                            int[] S, int index) {
        res.add(new ArrayList<Integer>(tmp));
        
        for (int i = index; i < S.length; i++) {
            tmp.add(S[i]);
            subsetHelp(res, tmp, S, i + 1);
            tmp.remove(tmp.size() - 1);
        }
    }
}

Given a collection of integers that might contain duplicates, S, return all possible subsets. Note: Elements in a subset must be in non-descending order. The solution set must not contain duplicate subsets.
一样DFS，但是对于相邻两个元素相同的情况下，必须避免重复case。

public class Solution {
    //Time: O(n^n)
    public ArrayList<ArrayList<Integer>> subsetsWithDup(int[] num) {
        ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
        ArrayList<Integer> tmp = new ArrayList<Integer>();
        Arrays.sort(num);
        subsetsHelp(res, tmp, num, 0);
        return res;
    }
    
    private void subsetsHelp(ArrayList<ArrayList<Integer>> res, ArrayList<Integer> tmp,
                             int[] num, int index) {
        res.add(new ArrayList<Integer>(tmp));
        
        for (int i = index; i < num.length; i++) {
            if (i != index && num[i] == num[i - 1]) {
                continue;
            }
            
            tmp.add(num[i]);
            subsetsHelp(res, tmp, num, i + 1);
            tmp.remove(tmp.size() - 1);
        }
    }
}

Minimum Depth of Binary Tree

Given a binary tree, find its minimum depth.

The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node.

DFS:

public class Solution {
    //Time: O(n)
    int min = Integer.MAX_VALUE;
    public int minDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        getMin(root, 1);
        return min;
    }
    
    private void getMin(TreeNode root, int depth) {
        if (root.left == null && root.right == null) {
            min = Math.min(min, depth);
        }
        
        if (root.left != null) {
            getMin(root.left, depth + 1);
        }
        if (root.right != null) {
            getMin(root.right, depth + 1);
        }
    }
}

BFS:

public class Solution {
    //Time: O(n)
    public int minDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        
        int length = 1;
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                TreeNode cur = queue.poll();
                if (cur.left != null) {
                    queue.offer(cur.left);
                }
                if (cur.right != null) {
                    queue.offer(cur.right);
                }
                if (cur.left == null && cur.right == null) {
                    return length;
                }
            }
            length++;
        }
        return length;
    }
}

Sum Root to Leaf Numbers

Given a binary tree containing digits from 0-9 only, each root-to-leaf path could represent a number.

An example is the root-to-leaf path 1->2->3 which represents the number 123.

Find the total sum of all root-to-leaf numbers.

For example,

    1

   /  \

  2   3

The root-to-leaf path 1->2 represents the number 12.
The root-to-leaf path 1->3 represents the number 13.

Return the sum = 12 + 13 = 25.

DFS: 

public class Solution {
    //Time: O(n)
    private int sum = 0;
    public int sumNumbers(TreeNode root) {
        if (root == null) {
            return sum;
        }
        getSum(root, 0);
        return sum;
    }
    
    private void getSum(TreeNode root, int cur) {
        cur = cur * 10 + root.val;
        if (root.left == null && root.right == null) {
            sum += cur;
            return;
        }
        if (root.left != null) {
            getSum(root.left, cur);
        }
        if (root.right != null) {
            getSum(root.right, cur);
        }
    }
}

BFS: 

public class Solution {
    //Time: O(n)
    public int sumNumbers(TreeNode root) {
        if (root == null) {
            return 0;
        }
        
        int sum = 0;
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        Queue<Integer> queuesum = new LinkedList<Integer>();
        queue.offer(root);
        queuesum.offer(root.val);
        
        while (!queue.isEmpty()) {
            TreeNode cur = queue.poll();
            int cursum = queuesum.poll();
            if (cur.left != null) {
                queue.offer(cur.left);
                queuesum.offer(cursum * 10 + cur.left.val);
            }
            if (cur.right != null) {
                queue.offer(cur.right);
                queuesum.offer(cursum * 10 + cur.right.val);
            }
            if (cur.left == null && cur.right == null) {
                sum += cursum;
            }
        }
        return sum;
    }
}

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],

]

DFS: 

public class Solution {
    //Time: O(n^k)
    public ArrayList<ArrayList<Integer>> combine(int n, int k) {
        ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
        ArrayList<Integer> tmp = new ArrayList<Integer>();
        combineHelp(res, tmp, n, k, 1);
        return res;
    }
    
    private void combineHelp(ArrayList<ArrayList<Integer>> res, ArrayList<Integer> tmp,
                             int n, int k, int index) {
        if (tmp.size() == k) {
            res.add(new ArrayList<Integer>(tmp));
            return;
        }          
        
        for (int i = index; i <= n; i++) {
            tmp.add(i);
            combineHelp(res, tmp, n, k, i + 1);
            tmp.remove(tmp.size() - 1);
        }
    }
}

Path Sum I && II

I: Given a binary tree and a sum, determine if the tree has a root-to-leaf path such that adding up all the values along the path equals the given sum.

For example:
Given the below binary tree and sum = 22,

              5
             / \
            4   8
           /   / \
          11  13  4
         /  \      \
        7    2      1

return true, as there exist a root-to-leaf path 5->4->11->2 which sum is 22.

DFS: 

public class Solution {
    //Time: O(n)
    public boolean hasPathSum(TreeNode root, int sum) {
        if (root == null) {
            return false;
        }
        return checkPath(root, root.val, sum);
    }
    
    private boolean checkPath(TreeNode root, int cur, int sum) {
        if (root.left == null && root.right == null) {
            if (cur == sum) {
                return true;
            }
            return false;
        }
        
        boolean left = false;
        boolean right = false;;
        if (root.left != null) {
            left = checkPath(root.left, cur + root.left.val, sum);
        }
        if (root.right != null) {
            right = checkPath(root.right, cur + root.right.val, sum);
        }
        return left || right;
    }
}

BFS: 

public class Solution {
    //Time: O(n)
    public boolean hasPathSum(TreeNode root, int sum) {
        if (root == null) {
            return false;
        }
        
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        Queue<Integer> queueSum = new LinkedList<Integer>();
        queue.offer(root);
        queueSum.offer(root.val);
        while (!queue.isEmpty()) {
            TreeNode cur = queue.poll();
            int cursum = queueSum.poll();
            if (cur.left != null) {
                queue.offer(cur.left);
                queueSum.offer(cursum + cur.left.val);
            }
            if (cur.right != null) {
                queue.offer(cur.right);
                queueSum.offer(cursum + cur.right.val);
            }
            if (cur.left == null && cur.right == null && cursum == sum) {
                return true;
            }
        }
        return false;
    }
}

Given a binary tree and a sum, find all root-to-leaf paths where each path's sum equals the given sum.

DFS: 

public class Solution {
    public ArrayList<ArrayList<Integer>> pathSum(TreeNode root, int sum) {
        ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
        if (root == null) {
            return res;
        }
        ArrayList<Integer> tmp = new ArrayList<Integer>();
        path(res, tmp, root, sum);
        return res;
    }
    
    private void path(ArrayList<ArrayList<Integer>> res, ArrayList<Integer> tmp,
                      TreeNode root, int sum) {
        if (root.left == null && root.right == null) {
            tmp.add(root.val);
            if (sum == root.val) {
                res.add(new ArrayList(tmp));
            }
            tmp.remove(tmp.size() - 1);
            return;
        }   
        
        tmp.add(root.val);
        if (root.left != null) {
            path(res, tmp, root.left, sum - root.val);
        }
        if (root.right != null) {
            path(res, tmp, root.right, sum - root.val);
        }
        tmp.remove(tmp.size() - 1);
    }
}

Permutations I && II

Given a collection of 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], and [3,2,1].

DFS，检查当前元素是否已经被加入。

public class Solution {
    //Time: O(n^n) 
    public ArrayList<ArrayList<Integer>> permute(int[] num) {
        ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
        if (num == null || num.length == 0) {
            return res;
        }
        ArrayList<Integer> temp = new ArrayList<Integer>();
        permuteHelp(res, temp, num);
        return res;
    }
    
    private void permuteHelp(ArrayList<ArrayList<Integer>> res, ArrayList<Integer> temp, int[] num) {
        if (temp.size() == num.length) {
            res.add(new ArrayList<Integer>(temp));
            return;
        }
        
        for (int i = 0; i < num.length; i++) {
            if (temp.contains(num[i])) {
                continue;
            }
            
            temp.add(num[i]);
            permuteHelp(res, temp, num);
            temp.remove(temp.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], and [2,1,1].

这题要考虑重复元素，需要一个boolean 数组来检查是否已经加入数组，同时对于相同的数字也要进行检测。

public class Solution {
    public ArrayList<ArrayList<Integer>> permuteUnique(int[] num) {
        ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
        ArrayList<Integer> tmp = new ArrayList<Integer>();
        Arrays.sort(num);
        boolean[] visit = new boolean[num.length];
        permutate(res, tmp, num, visit);
        return res;
    }
    
    private void permutate(ArrayList<ArrayList<Integer>> res, ArrayList<Integer> tmp, 
                           int[] num, boolean[] visit) {
        if (tmp.size() == num.length) {
            res.add(new ArrayList<Integer>(tmp));
            return;
        }
        
        for (int i = 0; i < num.length; i++) {
            if (visit[i] || (i != 0 && num[i] == num[i - 1] && !visit[i - 1])) {
                continue;
            }
            visit[i] = true;
            tmp.add(num[i]);
            permutate(res, tmp, num, visit);
            tmp.remove(tmp.size() - 1);
            visit[i] = false;
        }
    } 
}

N-Queens I && II

Given an integer n, return all distinct solutions to the n-queens puzzle.

DFS:

public class Solution {
    public ArrayList<String[]> solveNQueens(int n) {
        ArrayList<String[]> res = new ArrayList<String[]>();
        int[] rows = new int[n];
        solve(res, rows, 0);
        return res;
    }
    
    private void solve(ArrayList<String[]> res, int[] rows, int row) {
        if (row == rows.length) {
            String[] tmp = new String[rows.length];
            draw(rows, tmp);
            res.add(tmp);
            return;
        }
        
        for (int i = 0; i < rows.length; i++) {
            rows[row] = i;
            if (valid(rows, row)) {
                solve(res, rows, row + 1);
            }
        }
    }
    
    private boolean valid(int[] rows, int row) {
        for (int i = 0; i < row; i++) {
            if (rows[i] == rows[row]) {
                return false;
            }
            
            if (Math.abs(rows[row] - rows[i]) == Math.abs(row - i)) {
                return false;
            }
        }
        return true;
    }
    
    private void draw(int[] rows, String[] tmp) {
        for (int i = 0; i < tmp.length; i++) {
            StringBuilder cur = new StringBuilder();
            int pos = rows[i];
            for (int j = 0; j < pos; j++) {
                cur.append('.');
            }
            cur.append('Q');
            for (int j = pos + 1; j < tmp.length; j++) {
                cur.append('.');
            }
            tmp[i] = cur.toString();
        }
    }
}

Follow up for N-Queens problem.

Now, instead outputting board configurations, return the total number of distinct solutions.

经典的递归问题。用一个cols[]数组，cols[i]: i代表第几列，cols[i]代表在第i列的行数。同时还要检查在当前列当前行和之前比较是否合法。

public class Solution {
    //Time: O(n^n)  Space: O(n)
    private int num = 0;
    public int totalNQueens(int n) {
        int[] cols = new int[n];
        Nqueen(cols, 0);
        return num;
    }
    
    private void Nqueen(int[] cols, int col) {
        if (col == cols.length) {
            num++;
            return;
        }
        
        for (int i = 0; i < cols.length; i++) {
            cols[col] = i;
            if (valid(cols, col)) {
                Nqueen(cols, col + 1);
            }
        }
    }
    
    private boolean valid(int[] cols, int col) {
        for (int i = 0; i < col; i++) {
            if (cols[i] == cols[col]) {
                return false;
            }
            if (Math.abs(cols[col] - cols[i]) == Math.abs(col - i)) {
                return false;
            }
        }
        return true;
    }
}