How is backtracking different from dynamic programming?

Backtracking lists every answer. Dynamic programming counts or optimizes by reusing answers to repeated subproblems. If subproblems repeat, cache them.

How do I avoid duplicate results?

Sort the input, then skip a value that equals the one before it at the same depth. Each distinct choice is tried once.

Pattern · 14 problems

Backtracking Interview Problems

Backtracking builds an answer one choice at a time and undoes the choice afterward. Pruning keeps it affordable.

Get the link for your laptop Start with Combination Sum

Free: write the code and run it, no sign-up.

When I reach for it

The question asks for all combinations, permutations or placements.
You make a choice, explore it, and may need to take it back.
Brute force is exponential, and the interviewer expects that.

Problems, easiest first

0 easy · 10 medium · 4 hard. Open one to read it, then write it in the free editor.

The idea

Build the answer one choice at a time. If a choice breaks a rule, stop that branch early. After exploring a choice, undo it so the next one starts clean.

Answer three questions first. What is a choice? When is a path complete? When can I prune?

def search(start, path, remaining):
    if remaining == 0:
        results.append(path[:])            # copy: path keeps changing
        return
    for i in range(start, len(nums)):
        if nums[i] > remaining:
            continue                       # prune this branch
        path.append(nums[i])               # choose
        search(i, path, remaining - nums[i])   # explore; i allows reuse
        path.pop()                         # un-choose

Combinations that sum to a target. Choose, explore, un-choose. Copy the path when you record it. Python shown; the idea carries to every language in the editor.

Where it goes wrong

Recording the path itself instead of a copy of it.
Forgetting to undo the choice.
Duplicates in the input. Sort first and skip repeated values at the same level.

Say this before you type. Say the choice, the stopping rule, and the earliest moment you can prune.

Where Coco comes in

Coco is an AI study partner, not a person. She listens while you explain your code, asks what a line does and never hands you the fix. Sign in free to type with Coco, up to a daily limit, and to talk with her for one hour. After that, talking comes with the $79 pack. Anyone can open the editor and run their code.

Questions people ask

How is backtracking different from dynamic programming?: Backtracking lists every answer. Dynamic programming counts or optimizes by reusing answers to repeated subproblems. If subproblems repeat, cache them.
How do I avoid duplicate results?: Sort the input, then skip a value that equals the one before it at the same depth. Each distinct choice is tried once.

Meet these next

Fin and Coco are characters, not people. strongyes.io is independent. Leo builds it with AI agents.