Leetcode: Factor Combinations

Numbers can be regarded as product of its factors. For example,

8 = 2 x 2 x 2;
  = 2 x 4.

Write a function that takes an integer n and return all possible combinations of its factors.

Note: 

1. Each combination's factors must be sorted ascending, for example: The factors of 2 and 6 is [2, 6], not [6, 2].
2. You may assume that n is always positive.
3. Factors should be greater than 1 and less than n.

Examples: 
input: 1
output: 

[]

input: 37
output: 

[]

input: 12
output:

[
  [2, 6],
  [2, 2, 3],
  [3, 4]
]

input: 32
output:

[
  [2, 16],
  [2, 2, 8],
  [2, 2, 2, 4],
  [2, 2, 2, 2, 2],
  [2, 4, 4],
  [4, 8]
]

Code (Java):

public class Solution {
    public List<List<Integer>> getFactors(int n) {
        List<List<Integer>> result = new ArrayList<List<Integer>>();
        if (n <= 3) {
            return result;
        }
        
        List<Integer> curr = new ArrayList<Integer>();
        
        getFactorsHelper(n, n, 2, curr, result);
        
        return result;
    }
    
    private void getFactorsHelper(int ori, int n, int start, List<Integer> curr, List<List<Integer>> result) {
        if (n <= 1) {
            result.add(new ArrayList<Integer>(curr));
            return;
        }
        
        for (int i = start; i <= n && i < ori; i++) {
            if (n % i == 0) {
                curr.add(i);
                getFactorsHelper(ori, n / i, i, curr, result);
                curr.remove(curr.size() - 1);
            }
        }
    }
}

Update on 10/21/15:

public class Solution {
    public List<List<Integer>> getFactors(int n) {
        List<List<Integer>> result = new ArrayList<>();
        
        if (n <= 1) {
            return result;
        }
        
        List<Integer> curr = new ArrayList<>();
        
        getFactorsHelper(2, 1, n, curr, result);
        
        return result;
    }
    
    private void getFactorsHelper(int start, int product, int n, List<Integer> curr, List<List<Integer>> result) {
        if (start > n || product > n) {
            return;
        }
        
        if (product == n) {
            result.add(new ArrayList<Integer>(curr));
            return;
        }
        
        for (int i = start; i < n; i++) {
            if (i * product > n) {
                break;
            }
            
            if (n % (product * i) == 0) {
                curr.add(i);
                getFactorsHelper(i, product * i, n, curr, result);
                curr.remove(curr.size() - 1);
            }
        }
    }
}

Summary:
There is one trick in this problem. For each candidate factor we tried, we must make sure it is dividable by n. Thus we can avoid many unnecessary recursion calls. 

Leetcode: N-Queens II

Follow up for N-Queens problem.

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

Understand the problem:
This is an extension of the N-Queen I problem, but just asks for returning the number of solutions. 

Solution:

public class Solution {
    private int result = 0;
    public int totalNQueens(int n) {
        if (n == 0 || n == 2 || n == 3) {
            return 0;
        }
        int[] cols = new int[n];
        totalNQueensHelper(n, 0, cols);
        
        return result;
    }
    
    private void totalNQueensHelper(int n, int row, int[] cols) {
        if (row == n) {
            result++;
            return;
        }
        
        for (int j = 0; j < n; j++) {
            if (isValid(j, row, cols)) {
                cols[row] = j; 
                totalNQueensHelper(n, row + 1, cols);
            }
        }
    }
    
    private boolean isValid(int col, int rows, int[] cols) {
        for (int i = 0; i < rows; i++) {
            if (cols[i] == col || rows - i == Math.abs(cols[i] - col)) {
                return false;
            }
        }
        return true;
    }
}

Leetcode: Restore IP Addresses

Given a string containing only digits, restore it by returning all possible valid IP address combinations.

For example:
Given "25525511135",

return ["255.255.11.135", "255.255.111.35"]. (Order does not matter)

Understand the problem:
The problem gives a string containing only digits, restore by returning all possible valid IP addresses combinations. 

So the crux of the problem is to understand "what is a valid IP address"? A valid IP address has the format of xxx.xxx.xxx.xxx, where xxx is a number from 0 to 255. Note that there are some reserved IP addresses, but this problem only asks for the valid structure of the IP addresses. Therefore a valid IP address could range from 0.0.0.0 to 255.255.255.255. 

Recursive Solution:
This is another permutation and combination problem. 

Code (Java):

public class Solution {
    public List<String> restoreIpAddresses(String s) {
        List<String> result = new ArrayList<String>();
        
        if (s == null || s.length() < 4) {
            return result;
        }
        
        restoreHelper(s, 0, 1, "", result);
        
        return result;
    }
    
    private void restoreHelper(String s, int start, int segment, String curr, List<String> result) {
        if (start >= s.length()) {
            return;
        }
        
        if (segment == 4) {
            if (isValid(s.substring(start))) {
                result.add(curr + "." + s.substring(start));
            }
            return;
        }
        
        for (int i = 1; i < 4 && start + i < s.length(); i++) {
            String temp = s.substring(start, start + i);
            if (isValid(temp)) {
                if (segment == 1) {
                    restoreHelper(s, start + i, segment + 1, temp, result);
                } else {
                    restoreHelper(s, start + i, segment + 1, curr + "." + temp, result);
                }
            }
        }
    }
    
    private boolean isValid(String str) {
        if (str == null || str.length() > 3) {
            return false;
        }
        
        int num = Integer.parseInt(str);
        if (str.charAt(0) == '0' && str.length() > 1) {
            return false;
        }
        
        if (num >= 0 && num <= 255) {
            return true;
        }
        
        return false;
    }
}

Leetcode: Gray Code

The gray code is a binary numeral system where two successive values differ in only one bit.

Given a non-negative integer n representing the total number of bits in the code, print the sequence of gray code. A gray code sequence must begin with 0.

For example, given n = 2, return [0,1,3,2]. Its gray code sequence is:

00 - 0
01 - 1
11 - 3
10 - 2

Note:
For a given n, a gray code sequence is not uniquely defined.

For example, [0,2,3,1] is also a valid gray code sequence according to the above definition.

For now, the judge is able to judge based on one instance of gray code sequence. Sorry about that.

Understand of the problem:
The problem asks for outputting all Gray Code. For the background knowledge about the gray code, please refer the link 
http://zh.wikipedia.org/wiki/%E6%A0%BC%E9%9B%B7%E7%A0%81#.E4.BA.8C.E9.80.B2.E4.BD.8D.E6.95.B8.E8.BD.89.E6.A0.BC.E9.9B.B7.E7.A2.BC

For n = 1's Gray Code:
0
---
1

For n = 2 Gray Code:
00
01
-----
11
10

For n = 3 Gray Code:
000
001
011
010
----------
110
111
101
100

So we can see that for the Gray code sequence with n, it equals to (n - 1)'s Gray code sequence, as shown in the upper half the examples. The below halves are equal to the sum of n- 1 gray code plus the 1 << (n - 1), in backward order. 

Code (Java):

public class Solution {
    public List<Integer> grayCode(int n) {
        List<Integer> result = new ArrayList<Integer>();
        
        if (n == 0) {
            result.add(0);
            return result;
        }
        
        List<Integer> lastGray = grayCode(n - 1);
        int addOnNum = 1 << (n - 1);
        
        result.addAll(lastGray);
        
        for (int i = lastGray.size() - 1; i >= 0; i--) {
            result.add(lastGray.get(i) + addOnNum);
        }
        
        return result;
    }
}

Update on 8/1/2018:

class Solution {
    public List<Integer> grayCode(int n) {
        List<Integer> ans = new ArrayList<>();
        
        if (n <= 0) {
            ans.add(0);
            return ans;
        }
        
        ans.add(0);
        ans.add(1);
        
        for (int i = 2; i <= n; i++) {
            int size = ans.size();
            for (int j = size - 1; j >= 0; j--) {
                ans.add(ans.get(j) + (1 <<(i - 1)));
            }
        }
        
        return ans;
    }
}

Leetcode: Word Search

Given a 2D board and a word, find if the word exists in the grid.

The word can be constructed from letters of sequentially adjacent cell, where "adjacent" cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once.

For example,
Given board =

[
  ["ABCE"],
  ["SFCS"],
  ["ADEE"]
]

word = "ABCCED", -> returns true,
word = "SEE", -> returns true,
word = "ABCB", -> returns false.

Understand the problem:
The problem asks for if a Word exists in the board, where the word can be constructed from letters of sequentially adjacent cell. Note that the same letter cell may not be used more than once, which means the solution cannot contain a circle. 

Solution:
The problem could be still categorized as a permutation and combination problem. The only thing to note is each cell can only be visited once, so we need to use an array to mark each visited cell.

Code (Java):

public class Solution {
    public boolean exist(char[][] board, String word) {
        if (board == null || word == null) {
            return true;
        }
        
        if (board.length == 0 && word.length() == 0) {
            return true;
        }
        
        int rows = board.length;
        int cols = board[0].length;
        boolean[][] visited = new boolean[rows][cols];
        
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (existHelper(board, word, 0, i, j, visited)) {
                    return true;
                }
            }
        }
        return false;
    }
    
    private boolean existHelper(char[][] board, String word, int start, int row, int col, boolean[][] visited) {
        if (start == word.length()) {
            return true;
        }
        
        if (row < 0 || col < 0 || row >= board.length || col >= board[0].length) {
            return false;
        }
        
        if (visited[row][col]) {
            return false;
        }
        
        if (board[row][col] != word.charAt(start)) {
            return false;
        }
        
        visited[row][col] = true;
        boolean result = existHelper(board, word, start + 1, row - 1, col, visited) ||
                         existHelper(board, word, start + 1, row + 1, col, visited) ||
                         existHelper(board, word, start + 1, row, col - 1, visited) ||
                         existHelper(board, word, start + 1, row, col + 1, visited);
        visited[row][col] = false;
        
        return result;
    }
}

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

Understand the problem:
A classic permutation and combination problem. So using the recursion is a natural way. 

Solution:

public class Solution {
    public ArrayList<ArrayList<Integer>> combine(int n, int k) {
        ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
        if (n <= 0 || k <= 0 || n < k) {
            return result;
        }
        
        int[] num = new int[n];
        for (int i = 0; i < n; i++) {
            num[i] = i + 1;
        }
        ArrayList<Integer> curr = new ArrayList<Integer>();
        combineHelper(num, 0, 0, k, result, curr);
        
        return result;
    }
    
    private void combineHelper(int[] num, int start, int m, int k, 
        ArrayList<ArrayList<Integer>> result, ArrayList<Integer> curr) {

        if (m == k) {
            result.add(new ArrayList<Integer>(curr));
            return;
        }
        

        for (int i = start; i < num.length; i++) {
            curr.add(num[i]);
            combineHelper(num, i + 1, m + 1, k, result, curr);
            curr.remove(curr.size() - 1);
        }
    }
}

Update on 9/25/15:

public class Solution {
    public List<List<Integer>> combine(int n, int k) {
        List<List<Integer>> result = new ArrayList<List<Integer>>();
        if (n <= 0 || k <= 0 || n < k) {
            return result;
        }
        
        List<Integer> curr = new ArrayList<>();
        
        combineHelper(1, n, 0, k, curr, result);
        
        return result;
    }
    
    private void combineHelper(int start, int n, int num, int k, 
       List<Integer> curr, List<List<Integer>> result) {
        if (num == k) {
            result.add(new ArrayList<Integer>(curr));
            return;
        }
        
        for (int i = start; i <= n; i++) {
            curr.add(i);
            combineHelper(i + 1, n, num + 1, k, curr, result);
            curr.remove(curr.size() - 1);
        }
    }
}

Leetcode: Permutation Sequence

The set [1,2,3,…,n] contains a total of n! unique permutations.

By listing and labeling all of the permutations in order,
We get the following sequence (ie, for n = 3):

1. "123"
2. "132"
3. "213"
4. "231"
5. "312"
6. "321"

Given n and k, return the kth permutation sequence.

Note: Given n will be between 1 and 9 inclusive.

Understand the problem:
The problem asks for return the kth permutation sequence. This question could be very similar to the permutation problem, so we can use a counter to count for the kth sequence. 
The crux of the problem is the order, so if we simply swap the ith and start th of the element of the previous approach, it will not  output the sequence in order. For e.g. when n = 3, the output is 
123, 132, 213, 231, 321, 312. So when i - start > 1, we need to swap the following elements as well. 

Naive Solution:
So the naive solution is do the permutation "in-order" and note down the nth sequence. When it meets the kth sequence, return the kth sequence. 

public class Solution {
    int count = 0;
    public String getPermutation(int n, int k) {
        if (n <= 0 || k <= 0) {
            return "";
        }
        
        int num[] = new int[n];
        for (int i = 0; i < n; i++) {
            num[i] = i + 1;
        }
        
        getPermutationHelper(num, k, 0);
        
        return Arrays.toString(num);
    }
    
    private boolean getPermutationHelper(int[] num, int k, int start) {
        if (start >= num.length) {
            count++;
            if (count == k) {
                return true;
            }
            return false;
        }
        
        for (int i = start; i < num.length; i++) {
            for (int j = start; j < i; j++) {
                swap(num, j, i);
            }
            if (getPermutationHelper(num, k, start + 1) == true) {
                return true;
            }
            
            for (int j = i - 1; j >= start; j--) {
                swap(num, j, i);
            }
        }
        return false;
    }
    
    private void swap(int[] num, int i, int j) {
        int temp = num[i];
        num[i] = num[j];
        num[j] = temp;
    }
}

Discussion:
The time complexity of this solution is factorial, so it got the TLE error on OJ. We must find another faster way to solve this question. 

A better solution:

public class Solution {
    public String getPermutation(int n, int k) {
        if (n <= 0 || k <= 0) {
            return "";
        }
        
        ArrayList<Integer> num = new ArrayList<Integer>();
        for (int i = 1; i <= n; i++) {
            num.add(i);
        }
        
        // calculate the factorial
        int factorial = 1;
        for (int i = 1; i <= n; i++) {
            factorial *= i;
        }
        
        k--;
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < n; i++) {
            factorial /= (n - i);
            int index = k / factorial;
            sb.append(num.get(index));
            
            num.remove(index);
            
            // update current k
            k %= factorial;
        }
        
        return sb.toString();
    }
}

Leetcode: N-Queens

he n-queens puzzle is the problem of placing n queens on an n×n chessboard such that no two queens attack each other.

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

Each solution contains a distinct board configuration of the n-queens' placement, where 'Q' and '.' both indicate a queen and an empty space respectively.

For example,
There exist two distinct solutions to the 4-queens puzzle:

[
 [".Q..",  // Solution 1
  "...Q",
  "Q...",
  "..Q."],

 ["..Q.",  // Solution 2
  "Q...",
  "...Q",
  ".Q.."]
]

Understand the problem:
It is a classic N-queue problem. The eight queens puzzle is the problem of placing eight chess queens on an 8×8 chessboard so that no two queens threaten each other. Thus, a solution requires that no two queens share the same row, column, or diagonal. The eight queens puzzle is an example of the more general n-queens problem of placing n queens on an n×n chessboard, where solutions exist for all natural numbers n with the exception of n=2 or n=3. 

Solution:
This is again a classic permutation and combination problem. So we can still apply the same recursive approach. 

Code (Java):

public class Solution {
    public List<String[]> solveNQueens(int n) {
        List<String[]> result = new ArrayList<String[]>();
        
        if (n == 0 || n == 2 || n == 3) {
            return result;
        }
        
        solveNqueensHelper(n, 0, new int[n], result);
        
        return result;
    }
    
    private void solveNqueensHelper(int n, int row, int[] cols, List<String[]> result) {
        if (row == n) {
            String[] solution = new String[n];
            for (int i = 0; i < n; i++) {
                StringBuilder temp = new StringBuilder();
                for (int j = 0; j < n; j++) {
                    if (cols[i] == j) {
                        temp.append('Q');
                    } else {
                        temp.append('.');
                    }
                }
                solution[i] = temp.toString();
            }
            result.add(solution);
            return;
        }
        
        for (int j = 0; j < n; j++) {
            if (isValid(j, row, cols) == true) {
                cols[row] = j;
                solveNqueensHelper(n, row + 1, cols, result);
            }
        }
    }
    
    private boolean isValid(int col, int row, int[] cols) {
        for (int i = 0; i < row; i++) {
            if (col == cols[i] || row - i == Math.abs(col - cols[i])) {
                return false;
            }
        }
        return true;
    }
}

Leetcode: Combination Sum II

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] 

Understand the problem:
The problem is very similar to the last question, but each number in C can only be used once in the combination. So the solution is still DFS. 

Solution:

public class Solution {
    public ArrayList<ArrayList<Integer>> combinationSum2(int[] num, int target) {
        ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
        if (num == null || num.length == 0) {
            return result;
        }
        
        Arrays.sort(num);
        
        combinationSumHelper(num, target, 0, 0, new ArrayList<Integer>(), result);
        
        return result;
    }
    
    private void combinationSumHelper(int[] num, int target, int start, int sum, 
　　　　　ArrayList<Integer> curr, ArrayList<ArrayList<Integer>> result) {
        if (sum == target) {
            result.add(new ArrayList<Integer>(curr));
            return;
        }
        
        if (sum > target) {
            return;
        }
        
        for (int i = start; i < num.length; i++) {
            if (i != start && num[i - 1] == num[i]) {
                continue;
            }
            if ((sum + num[i]) > target) {
                break;
            } 
            
            sum += num[i];
            curr.add(num[i]);
            
            combinationSumHelper(num, target, i + 1, sum, curr, result);
            
            sum -= num[i];
            curr.remove(curr.size() - 1);
        }
    }
}

Summary:
This question has a pitfall. For any permutation and combination problems in the code interview, you must first clarify with the interviewer that if the set contains duplicates. If yes, all duplicated numbers can be only traversed once. 

Leetcode: 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] 

Understand the problem:
The problem asks for finding all unique combinations where the candidate numbers sums to the target. Note that same number can be used with unlimited number of times. There are also several special requirements in the problem. There are no negative numbers in the list, and the output should be in non-descending order. In addition, the solution set must not contain duplicate combinations. 

Solution:
This question could be categorized into permutation and combination problem, where DFS should be used to produce the solution. 

Code (Java):

public class Solution {
    public ArrayList<ArrayList<Integer>> combinationSum(int[] candidates, int target) {
        ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
        if (candidates == null || candidates.length == 0) {
            return result;
        }
        
        Arrays.sort(candidates);
        
        combinationSumHelper(candidates, target, 0, new ArrayList<Integer>(), 0, result);
        
        return result;
    }
    
    private void combinationSumHelper(int[] candidates, int target, int sum, 
　　　　　ArrayList<Integer> curr, int start, ArrayList<ArrayList<Integer>> result) {
        if (sum == target) {
            result.add(new ArrayList<Integer>(curr));
            return;
        }
        
        if (sum > target) {
            return;
        }
        
        for (int i = start; i < candidates.length; i++) {
            if (sum + candidates[i] > target) break;
            sum += candidates[i];
            curr.add(candidates[i]);
            
            combinationSumHelper(candidates, target, sum, curr, i, result);
            
            sum -= candidates[i];
            curr.remove(curr.size() - 1);
        }
    }
}

Discussion:
The time complexity for this question is exponential, since it is a NP problem. 

Summary:
This problem can be categorized into permutation and combination problems. Using the DFS is the key to solution. Draw a recursion tree will also help at understanding the idea as well.

Leetcode: Next Permutation

implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers.

If such arrangement is not possible, it must rearrange it as the lowest possible order (ie, sorted in ascending order).

The replacement must be in-place, do not allocate extra memory.

Here are some examples. Inputs are in the left-hand column and its corresponding outputs are in the right-hand column.
1,2,3 → 1,3,2
3,2,1 → 1,2,3
1,1,5 → 1,5,1

Understand the problem:
The problem is a little a bit harder to understand. So you must first understand what is the lexicographical order. Basically, the lexicographic or lexicographical order (also known as lexical order, dictionary order, alphabetical order or lexicographic(al) product) is a generalization of the way the alphabetical order of words is based on the alphabetical order of their component letters.

The next permutation means the next greater permutation of numbers according to the lexicographical order. For example, for the input 1 2 3, its permutations according to the lexicographical order is
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1
So its next permutation is 1 3 2. Since list in decreasing order is already the greatest, its next available permutation will be wrapped around to 1 2 3.

Solution:
Since we know at for a words in ascending order must be the smallest lexicographical order, while in descending order is the greatest lexicographical order. 

So we can iterate through the input string from end in reverse order, and find the first descending number. Mark that index. Then scan through the numbers after the number we found, until we find the smallest number which is still greater than the number we found. Since the string after the number is in descending order, it is pretty easy to find this number. We then swap this numbers. At least, we make all numbers behind the first number we found as in ascending order. 

Code (Java):

public class Solution {
    public void nextPermutation(int[] num) {
        if (num == null || num.length == 0) {
            return;
        }
        
        int i, j;
        for (i = num.length - 2; i >= 0; i--) {
            if (num[i] < num[i + 1]) {
                break;
            }
        }
        
        // for the case where the num[] is in descending order
        if (i >= 0) {
            for (j = i + 1; j < num.length; j++) {
                if (num[j] <= num[i]) {
                    break;
                }
            }
            j = j - 1;
            swap(num, i, j);
        }
        reverse(num, i + 1);
    }
    
    private void swap(int[] num, int i, int j) {
        int temp = num[i];
        num[i] = num[j];
        num[j] = temp;
    }
    
    private void reverse(int[] num, int start) {
        int end = num.length - 1;
        while (start < end) {
            int temp = num[start];
            num[start] = num[end];
            num[end] = temp;
            
            start++;
            end--;
        }
    }
}

Discussion:
We scan the array three times, so the time complexity is still O(n). Space complexity is O(1) since we don't use additional space. 

Summary:
The crux of the problem is to figure out what is the lexicographical order. After we know this, we scan from the end in reverse order. We scan from end because we wanna get the next greater permutation. We wanna find the ascending order numbers because if we get that, we know that the next permutation will be after that number.  We also need to figure out the smallest number which is greater than the number we found, and swap them. At least, we shall sort the numbers after i in ascending order. 

Leetcode: 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.

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.

Understand the problem:
The problem gives a digit string, return all possible letter combination that the number could represent. Note the the relative order of the number should be reflated in the corresponding strings. For instance, "23", 2 is ahead of 3, so abc should be in front of def as well. For a brute force solution, we can iterate all possible combinations, with the time complexity of O(n^m), where n is the number of characters for each digit, m is the length of the digit string. 

Recursive Solution:
It is a typical recursive problem, you can mimic the solution of Subset. 

Code (Java):

public class Solution {
    public ArrayList<String> letterCombinations(String digits) {
        ArrayList<String> result = new ArrayList<String>();
        
        if (digits == null) return result;
        
        String[] dict = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
        
        StringBuilder sb = new StringBuilder();
        letterCombinationsHelper(digits, 0, sb, dict, result);
        
        return result;
    }
    
    private void letterCombinationsHelper(String digits, int start, StringBuilder temp, String[] dict, ArrayList<String> result) {
        if (start >= digits.length()) {
            result.add(temp.toString());
            return;
        }
        
        // char to int
        int num = digits.charAt(start) - '0';
        for (int i = 0; i < dict[num].length(); i++) {
            temp.append(dict[num].charAt(i));
            letterCombinationsHelper(digits, start + 1, temp, dict, result);
            temp.deleteCharAt(temp.length() - 1);
        }
    }
}

Summary:
This is a very classical permutation and combination problem. All P&C problems share the similar idea of using DFS. Be cautious about that. 

Leetcode: Generate Parentheses

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

For example, given n = 3, a solution set is:

"((()))", "(()())", "(())()", "()(())", "()()()"

Understand the problem:
The problem asks to generate all combinations of well-formed parentheses. 
So the first question is what is a well formed parentheses? Basically, it must start from left parentheses and end with right parentheses. In addition, the number of left parentheses must be equal to right parentheses. Let's take several examples to illustrate this:
For n = 0, return empty
For n = 1, return ()
For n = 2, return ()(), (()).
For n = 3, return as above.

Solution:
The crux of the problem is for a valid parentheses, at any point the visited left parentheses should be greater or equal than the visited right parentheses. For example, ()()(),  at position 2, the number of left parentheses is 2 while the right one is 1. That helps to avoid the case such that () ), which could never be a valid parentheses. 
There is a good post illustrated the problem very well http://blog.csdn.net/fightforyourdream/article/details/14159435

For n = 3, we can draw a recursion tree to help understand the problem. Since the answer must start with left parentheses, the tree looks like:

  

So the solution could be recursive as well. We count the number of left and right parentheses visited. If both are equal to the n, we add the result into the result list. 

Code (Java):

public class Solution {
    public ArrayList<String> generateParenthesis(int n) {
        ArrayList<String> result = new ArrayList<String>();
        if (n <= 0) return result;
        
        StringBuilder sb = new StringBuilder();
        
        generateParenthesisHelper(n, 0, 0, sb, result);
        
        return result;
    }
    
    private void generateParenthesisHelper(int n, int left, int right, StringBuilder temp, ArrayList<String> result) {
        if (left < right) return;
        
        if (left == n && right == n) {
            result.add(temp.toString());
            return;
        }
        
        if (left < n) {
            temp.append('(');
            generateParenthesisHelper(n, left + 1, right, temp, result);
            temp.deleteCharAt(temp.length() - 1);
        }
        
        if (right < n) {
            temp.append(')');
            generateParenthesisHelper(n, left, right + 1, temp, result);
            temp.deleteCharAt(temp.length() - 1);
        }
    }
}

Summary:
The take away message is for the recursion problem, drawing a recursion tree could be very helpful to understand the problem. 

Leetcode: Subsets II

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.

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

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

Understand the problem:
This is an extension of the last problem. The major difference is the array contains duplicates. It asks for returning all distant subsets. 

For the input S = [1, 2, 2], if we use exactly the same approach as the last problem, what shall we get?

Solution:
Similar to the permutation II, we check the range from start to i contains duplicated numbers, if yes, simply jump to next iteration.

Code (Java):

public class Solution {
    public ArrayList<ArrayList<Integer>> subsetsWithDup(int[] num) {
        ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
        if (num == null || num.length == 0) return result;
        
        Arrays.sort(num);
        
        result.add(new ArrayList<Integer>());
        ArrayList<Integer> temp = new ArrayList<Integer>();
        
        subsetsHelper(num, 0, temp, result);
        
        return result;
    }
    
    private void subsetsHelper(int[] num, int start, ArrayList<Integer> temp, ArrayList<ArrayList<Integer>> result) {
        if (start >= num.length) return;
        
        for (int i = start; i < num.length; i++) {
            if (!isDup(num, start, i)) {
                temp.add(num[i]);
                result.add(new ArrayList<Integer>(temp));
                subsetsHelper(num, i + 1, temp, result);
                
                temp.remove(temp.size() - 1);
            }
        }
    }
    
    private boolean isDup(int[] num, int start, int end) {
        for (int i = start; i <= end - 1; i++) {
            if (num[i] == num[end]) return true;
        }
        return false;
    }
}

Discussion:
This problem has time complexity of O(2^n), since finding all subsets of a set is a NP problem.

Summary:
The take away message is all permutation and combination questions share very similar ways of solution. Make sure to understand the details.

Leetcode: 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],
  []
]

Understand the problem:
As described in the problem, given a set of DISTINCT integers, S, return all possible subsets. Elements in a subset must be in non-descending order. The solution set must not contain duplicate subsets. 


Recursive Solution:

public class Solution {
    public ArrayList<ArrayList<Integer>> subsets(int[] S) {
        ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
        if (S == null || S.length == 0) return result;
        
        Arrays.sort(S);
        
        result.add(new ArrayList<Integer>());
        
        ArrayList<Integer> temp = new ArrayList<Integer>();
        subsetsHelper(S, 0, result, temp);
        
        return result;
    }
    
    private void subsetsHelper(int[] S, int start, ArrayList<ArrayList<Integer>> result, ArrayList<Integer> temp) {
        if (start >= S.length) return;
        
        for (int i = start; i < S.length; i++) {
            temp.add(S[i]);
            result.add(new ArrayList<Integer>(temp));
            subsetsHelper(S, i + 1, result, temp);
            
            temp.remove(temp.size() - 1);
        }
    }
}

Leetcode: Permutation II

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

Understand the problem:
The problem is an extension to Permutation I, the mainly difference is it exists the duplicated elements, and we return only unique permutations. 

Solution:
The solution is very similar to the permutation I, the only difference is before we swap the number start and i, we check if between start and i has duplicates. If yes, it indicates that we visited the number before, so simply jump to next iteration.

Code (Java):

public class Solution {
    public ArrayList<ArrayList<Integer>> permuteUnique(int[] num) {
        ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
        
        permuteUnique(num, 0, result);
        
        return result;
    }
    
    private void permuteUnique(int[] num, int start, ArrayList<ArrayList<Integer>> result) {
        if (start >= num.length) {
            ArrayList<Integer> temp = toArrayList(num);
            result.add(temp);
            return;
        }
        
        for (int i = start; i < num.length; i++) {
            if (!containsDup(num, start, i)) {
                swap(num, i, start);
                permuteUnique(num, start + 1, result);
                swap(num, i, start);
            }
        }
    }
    
    private void swap(int[] num, int i, int j) {
        int temp = num[i];
        num[i] = num[j];
        num[j] = temp;
    }
    
    private ArrayList<Integer> toArrayList(int[] num) {
        ArrayList<Integer> temp = new ArrayList<Integer>(num.length);
        for (int i = 0; i < num.length; i++) {
            temp.add(num[i]);
        }
        return temp;
    }
    
    private boolean containsDup(int[] num, int start, int end) {
        for (int i = start; i <= end - 1; i++) {
            if (num[i] == num[end]) return true;
        }
        return false;
    }
}

Discussion:
Note the method on how to determine the duplicates. This the most tricky part of this problem.

Update on 07/29/18:

class Solution {
    public List<List<Integer>> permuteUnique(int[] nums) {
        List<List<Integer>> ans = new ArrayList<>();
        
        if (nums == null || nums.length == 0) {
            return ans;
        }
        
        Arrays.sort(nums);
        
        permuteHelper(0, nums, ans);
        
        return ans;
    }
    
    private void permuteHelper(int start, int[] nums, List<List<Integer>> ans) {
        if (start >= nums.length) {
            ans.add(new ArrayList<>(Arrays.stream(nums).boxed().collect(Collectors.toList())));
            return;
        }
        
        Set<Integer> set = new HashSet<>();
        for (int i = start; i < nums.length; i++) {
            if (set.add(nums[i])) {
                swap(nums, i, start);
                permuteHelper(start + 1, nums, ans);
                swap(nums, i, start);
            }
        }
    }
    
    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}

Update 5/7/19:

public class Solution {
    /*
     * @param :  A list of integers
     * @return: A list of unique permutations
     */
    public List<List<Integer>> permuteUnique(int[] nums) {
        // write your code here
        List<List<Integer>> ans = new ArrayList<>();
        if (nums == null || nums.length == 0) {
            ans.add(new ArrayList<Integer>());
            return ans;
        }

        Arrays.sort(nums);

        boolean[] visited = new boolean[nums.length];
        permuteUniqueHelper(nums, visited, new ArrayList<Integer>(), ans);
        return ans;
    }

    private void permuteUniqueHelper(int[] nums, boolean[] visited, List<Integer> curList, List<List<Integer>> ans) {
        if (curList.size() == nums.length) {
            ans.add(new ArrayList<>(curList));
            return;
        }

        for (int i = 0; i < nums.length; i++) {
            if (visited[i]) {
                continue;
            }
            if (i != 0 && nums[i] == nums[i - 1] && !visited[i - 1]) {
                continue;
            }

            visited[i] = true;
            curList.add(nums[i]);
            permuteUniqueHelper(nums, visited, curList, ans);
            visited[i] = false;
            curList.remove(curList.size() - 1);
        }
    }
}