10. Backtracking (Days 135—145)

Backtracking Template

def backtrack(path, choices, result):
    if is_solution(path):
        result.append(path[:])   # shallow copy
        return
    for choice in choices:
        if is_valid(choice):
            path.append(choice)
            backtrack(path, choices, result)
            path.pop()            # undo

Permutations

def permute(nums):
    result = []
    def backtrack(path, remaining):
        if not remaining:
            result.append(path[:])
            return
        for i in range(len(remaining)):
            path.append(remaining[i])
            backtrack(path, remaining[:i] + remaining[i+1:])
            path.pop()
    backtrack([], nums)
    return result

Generate Parentheses

// Java
public List<String> generateParenthesis(int n) {
    List<String> res = new ArrayList<>();
    backtrack(res, "", 0, 0, n);
    return res;
}
void backtrack(List<String> res, String curr, int open, int close, int max) {
    if (curr.length() == max * 2) { res.add(curr); return; }
    if (open < max) backtrack(res, curr + "(", open+1, close, max);
    if (close < open) backtrack(res, curr + ")", open, close+1, max);
}

More Problems