Template: 9. BACKTRACKING — Universal Template

9. BACKTRACKING — Universal Template

# =============================================================================
def backtrack(candidates, start, path, result):
    if is_goal(path):
        result.append(path[:])  # COPY the path
        return
    for i in range(start, len(candidates)):
        # Skip duplicates: if candidates[i] == candidates[i-1] and i > start: continue
        if is_valid(candidates[i], path):
            path.append(candidates[i])       # CHOOSE
            backtrack(candidates, i + 1, path, result)  # EXPLORE (i+1 for no reuse, i for reuse)
            path.pop()                        # UNCHOOSE

def is_goal(path):
    pass  # define your goal condition

def is_valid(choice, path):
    return True  # define your pruning condition


# =============================================================================