Recursion

经典题目

78 Subsets

	/*
		Method 1 : Recursion
		
		Do recursion based on index
		For each index, we have two choices:
			1. append the current num to list
			2. do nothing.
	*/
public List<List<Integer>> subsets(int[] nums) {
    List<List<Integer>> ans = new ArrayList<>();
    List<Integer> cur = new ArrayList<>();
    helper(nums, 0, cur, ans);
    return ans;
}
private void helper(int[] nums, int index, List<Integer> cur, List<List<Integer>> ans) {
    if (index == nums.length) {
        ans.add(new ArrayList<>(cur));
        return;
    }
    // Choice 1: don't append current num
    helper(nums, index + 1, cur, ans);
		// Choice 2: append current num
    cur.add(nums[index]);
    helper(nums, index + 1, cur, ans);
		// backtrack
    cur.remove(cur.size() - 1);
}

Eight Queens (CC189) 51 N-Queens

List<List<Integer>> solution() {
	EightQueens eq = new EightQueens();
	return eq.getArrangement();
}

class EightQueens {
	private int n = 8;
	private List<List<Integer>> rs;

	public EightQueens() {
		rs = new ArrayList<List<Integer>>();
	}

	public List<List<Integer>> getArrangement() {
		List<Integer> curr = new ArrayList<>();
		boolean[] rows = new boolean[n];
		boolean[] cols = new boolean[n];
		boolean[] diag = new boolean[2 * n - 1];
		boolean[] revDiag = new boolean[2 * n - 1];

		helper(0, curr, rs, rows, cols, diag, revDiag);
		return rs;
	}

	private void helper(int row, List<Integer> curr, List<List<Integer>> rs, boolean[] rows, boolean[] cols, boolean[] diag, boolean[] revDiag) {
		if(row == n) {
			rs.add(new ArrayList<Integer>(curr));
			return;
		}

		for(int col = 0; col < 8; col++) {
			if(valid(row, col, rows, cols, diag, revDiag)) {
				mark(row, col, rows, cols, diag, revDiag);
				curr.add(col);
				helper(row + 1, curr, rs, rows, cols, diag, revDiag);
				curr.remove(curr.size() - 1);
				unmark(row, col, rows, cols, diag, revDiag);
			}
		}
	}

	private boolean valid(int row, int col, boolean[] rows, boolean[] cols, boolean[] diag, boolean[] revDiag) {
		return !rows[row] && !cols[col] && !diag[row + col] && !revDiag[col + n - 1 - row];
	}

	private void mark(int row, int col, boolean[] rows, boolean[] cols, boolean[] diag, boolean[] revDiag) {
		rows[row] = true;
		cols[col] = true;
		diag[row + col] = true;
		revDiag[col + n - 1 - row] = true;
	}

	private void unmark(int row, int col, boolean[] rows, boolean[] cols, boolean[] diag, boolean[] revDiag) {
		rows[row] = false;
		cols[col] = false;
		diag[row + col] = false;
		revDiag[col + n - 1 - row] = false;
	}
}

Towers of Hanoi (CC189)

In the classic problem of the Tower of Hanoi, you have 3 towers and N disks of different sizes which can slide onto any tower. The puzzle starts with disks sorted in ascending order of size from top to bottom (i.e., each disk sits on top of an even larger one). You have the following constraints: 1) Only one disk can be moved at a time. 2) A disk is slid off the top of one tower onto another tower 3) A disk cannot be placed on top of a smaller disk. Write a program to move the disks from the first tower to the last using stacks.

/*
This problem is good candidate for the base case and build approach.

Case n = 1, we just simply move Disk 1 from T1 to T3.
Case n = 2, we could first move Disk 1 from T1 to T2, then move Disk 2 from T1 to T3, 
        then move Disk 1 from T2 to T3. Actually, T2 acts as a buffer in the above steps, 
        holding a disk while we move other disks to T3.
Case n = 3, we now know how to move two disks from T1 to T3, 
        we could just apply this approach and move two disks from T1 to T2, 
        and move Disk 3 from T1 to T3, and then apply the approach of moving 
        two disks again and move two disks from T2 to T3.
Case n = 4, same logic as n = 3.
*/

class Tower {
    private Stack<Integer> disks;
    private int index;

    public Tower(int i) {
        disks = new Stack<Integer>();
        index = i;
    }

    public int getIndex() {
        return index;    
    }

    public void add(int d) {
        if(!disks.isEmpty() && disks.peek() <= d) {
            System.out.println("Error placing disk " + d);
        } else {
            disks.push(d);
        }
    }

    public void moveTopTo(Tower t) {
        int top = disks.pop();
        t.add(top);
    }

    public void moveDisks(int n, Tower destination, Tower buffer) {
        if(n > 0) {
            moveDisks(n - 1, buffer, destination);
            moveTopTo(destination);
            buffer.moveDisks(n - 1, destination, this);
        }
    }
}


void main(String[] args) {
    int n = 3;
    Tower[] towers = new Tower[n];
    for(int i = 0; i < n; i++) {
        towers[i] = new Tower(i);
    }
    
    for(int i = n - 1; i >= 0; i--) {
        towers[0].add(i);
    }
    
    tower[0].moveDisks(n, towers[2], towers[1]);
}

Boolean Evaluation (CC189)

Given a boolean expression consisting of the symbols 0 (false), 1 (true), & (AND), | (OR), and ^ (XOR), and a desired boolean result value result, implement a function to count the number of ways of parenthesizing the expression such that it evaluates to result. The expression should be fully parenthesized (e.g., (0) ^ (1)) but not extraneously (e.g., ((0) ^ (1))).

// EXAMPLE
// countEval("1^0|0|1", false) -> 2
// countEval("0&0&0&1^1|0", true) -> 10

int countEval(String s, boolean result, HashMap<String, Integer> memo) {
	if(s.length == 0) return 0;
	if(s.length == 1) return stringToBool(s) == result ? 1 : 0;

	if(memo.containsKey(result + s)) {
		return memo.get(result + s);
	}

	int ways = 0;

	for(int i = 1; i < s.length(); i += 2) {
		char c = s.charAt(i);
		String left = s.substring(0, i);
		String right = s.substring(i + 1);

		int leftTrue = countEval(left, true, memo);
		int leftFalse = countEval(left, false, memo);
		int rightTrue = countEval(right, true, memo);
		int rightFalse = countEval(right, false, memo);
		int total = (leftTrue + leftFalse) * (rightTrue + rightFalse);

		int totalTrue = 0;
		if(c == '^') {
			totalTrue = leftTrue * rightFalse + leftFalse * rightTrue;
		} else if (c == '&') {
			totalTrue = leftTrue * rightTrue;
		} else if (c == '|') {
			totalTrue = leftTrue * rightFalse + leftFalse * rightTrue + leftTrue * rightTrue;
		}

		int subWays = result ? totalTrue : total - totalTrue;
		ways += subWays;
	}

	memo.put(result + s, ways);
	return ways;
}

boolean stringToBool(String c) {
	return c.equals("0") ? false : true;
}

884 Decoded String at Index

/*
	Method 1: Iterative.
	Memory Limit Exceed.

	Method 2: Recursion.
	The idea is if we meet a number, we only calculate the exact string length, once it reaches or exceeds K, we do a module operation to K,
	because our final answer would be at somewhere in S[0, i - 1].
	If we meed a letter, we just need to check whether we reach K.
*/
public String decodeAtIndex(String S, int K) {
    long cur = 0;
    for (int i = 0; i < S.length(); i++) {
        char c = S.charAt(i);
        if (c >= '2' && c <= '9') {
            int count = c - '0';
            if (cur * count >= K) {
                String str = S.substring(0, i);
                return decodeAtIndex(str, (int)((K - 1) % cur + 1));
            } else {
                cur *= count;
            }
        } else {
            cur += 1;
            if (cur == K) {
                return S.substring(i, i + 1);
            }
        }
    }
    return "";
}

679 24 Game

class Solution {
	/*
		Method 1: Recursion
		
		Total number of possibilities is 12 * 6 * 2 * 4 * 4 * 4.
		First, pick 2 numbers from 4 numbers (with order) => 12, then perform one operation => 4. Then put the result back to the number set.
		Second, pick 2 numbers from 3 numbers (one is the result of first step) => 6, then perform one operation => 4. Put the result back.
		Third, pick 2 numbers from 2 numbers => 2, perform one operation => 4.
		
		The idea of recursion:
		Recursively, pick 2 numbers from the nums list, perform one operation to get a result, then put the result and remaining numbers of nums list to a new list.
		
		'+' and '*' are commutative, while '-' and '/' are not.
		We can take advantage of the commutative property and skip the duplicate calculation.
		
		Be careful of performing '/', we need to be sure that denominator is not 0.
		
	*/
	
    public boolean judgePoint24(int[] nums) {
        List<Double> list = new ArrayList<>();
        for (int num : nums) {
            list.add((double) num);
        }
        return cal(list);
    }
    
    private boolean cal(List<Double> nums, List<String> path) {
        if (nums == null || nums.size() == 0) return false;
        if (nums.size() == 1) return Math.abs(nums.get(0) - 24) < 1e-6;	// double type, so we simply do approximate comparison.
        for (int i = 0; i < nums.size(); i++) {
            for (int j = 0; j < nums.size(); j++) {
                if (i != j) {
                    List<Double> next = new ArrayList<>();
                    for (int k = 0; k < nums.size(); k++) {
                        if (k != i && k != j) next.add(nums.get(k));
                    }
                    for (int k = 0; k < 4; k++) {
                        if (k < 2 && j > i) continue;	// '+' and '*' are commutative, so we skip
                        if (k == 0) next.add(nums.get(i) + nums.get(j));
                        if (k == 1) next.add(nums.get(i) * nums.get(j));
                        if (k == 2) next.add(nums.get(i) - nums.get(j));
                        if (k == 3) {
                            if (nums.get(j) != 0) {
                                next.add(nums.get(i) / nums.get(j));
                            } else {
                                continue;	// denominator = 0, so we skip
                            }
                        }
                        if (cal(next, nextPath)) return true;
                        next.remove(next.size() - 1);	// backtracking
                    }
                }
            }
        }
        return false;
    }
}