Backtracking - Quick Notes

#backtracking #neetcode

Every backtracking problem is essentially a DFS.
Backtracking has 4 pattern:

https://drive.google.com/file/d/1vfKpbaYkpGFrjxYaswa3ZBG0GZ-w58v5/view?t=19

Subset, combination and permutations

Here's a clear and concise breakdown of subset, combination, and permutation in the context of an array:

🔹 Subset:

A subset is any selection of elements (including the empty set and full set), where order does not matter, and elements may be excluded.

🔹 Combination:

A combination is a selection of k elements from the array, where order does not matter, and no repetition.

🔹 Permutation:

A permutation is an arrangement of k elements from the array, where order matters, and no repetition.

Summary Table

Combinations are subsets of size k where order does not matter.

Term Includes All Sizes? Order Matters? Repeats? Example from [1,2,3] (k=2)
Subset (2^n) Yes No No [], [1], [2], [3], [1,2], [1,3], [2,3], [1,2,3]`.
Combination No (fixed size k) No No [1,2], [1,3], [2,3]
Permutation No (fixed size k) Yes No [1,2], [2,1], [1,3], [3,1]

Notes

Neetcode 250 got 17 backtracking problems, out of these - 2 are not really backtracking!

  1. Warm-ups - Subsets without duplicates elements - 2 questions:

  2. Unique Subsets with duplicate elements - 1 question:

  1. Combination Target problems - 2 problems
    - Key
    - Usual array element branching will result into duplicate combinations.
    - Take "diminishing" Target as your main entity for base conditions
    - Problems:

    • https://neetcode.io/problems/combination-target-sum

      • This problem has unique tree because of condition "No duplicate combinations"
      • Notice how we handled "The same number may be chosen from nums an unlimited number of times." condition of problem by calling the dfs again with same index
      • Time and space: O(2^t) - t is target and height of tree
        Pasted image 20250519163413.png
        Pasted image 20250527174710.png

    • https://neetcode.io/problems/combination-target-sum-ii (Duplicate variation with "once" usage)

      • Think why duplicates are coming and how to avoid? (same as subsets)
      • Diff from above problem - Each number in candidates may only be used once in the combination.
      • Pasted image 20250519163946.png

  2. Combinations of Natural numbers - 1 problem
    - Problems:
    - https://neetcode.io/solutions/combinations
    - Like duplicate probs above, here too we might end up with duplicate combinations, but here the trick to avoid dups is - to not go back to left/prev values. for 1, try with 2,3,4 - but for 2- try with 3,4 only
    - Pasted image 20250519164909.png
    Pasted image 20250519164430.png
    Pasted image 20250519165712.png

  3. ⭐Permutations of Array:

    • Problems:

    • Time complexity: O(n!∗n)O(n!∗n)

    • Space complexity: O(n!∗n)O(n!∗n) for the output list.

  4. Word Search - Start a DFS from every cell

    • Problem - https://neetcode.io/problems/search-for-word
      • Start a DFS from every cell. Use Stack/path as Set because this time not only we want to keep track of journey - we also want "not to go to a seen node in current stack journey".
        image

  5. Palindrome Partitioning - https://neetcode.io/problems/palindrome-partitioning
    image

image

  1. N-Queens and N Queens II - 2 problems
    • Problems
    • N Queens
      • Three sets: columns, positive diagonals, negative diagonals
      • Go row wise
      • Time complexity: O(n!)
      • Space complexity: O(n^2)
      • Code highlights
        • How they built initial array
        • How they built output from board
        • clean-up and backtracking
        • base condition
class Solution {
    /**
     * @param {number} n
     * @return {string[][]}
     */
    solveNQueens(n) {
        const col = new Set();
        const posDiag = new Set();
        const negDiag = new Set();

        const res = [];
        const board = Array.from({ length: n }, 
                      () => Array(n).fill('.'));

        /**
         * @param {number} r
         * @return {void}
         */
        function backtrack(r) {
            if (r === n) {
                res.push(board.map(row => row.join('')));
                return;
            }

            for (let c = 0; c < n; c++) {
                if (col.has(c) || posDiag.has(r + c) ||
                    negDiag.has(r - c)) {
                    continue;
                }

                col.add(c);
                posDiag.add(r + c);
                negDiag.add(r - c);
                board[r][c] = 'Q';

                backtrack(r + 1);

                col.delete(c);
                posDiag.delete(r + c);
                negDiag.delete(r - c);
                board[r][c] = '.';
            }
        }

        backtrack(0);
        return res;
    }
}

class Solution {
    /**
     * @param {number} n
     * @return {number}
     */
    totalNQueens(n) {
        const col = new Set();
        const posDiag = new Set();
        const negDiag = new Set();
        let res = 0;

        /**
         * @param {number} r
         * @return {void}
         */
        function backtrack(r) {
            if (r === n) {
                res++;
                return;
            }

            for (let c = 0; c < n; c++) {
                if (col.has(c) || posDiag.has(r + c) ||
                    negDiag.has(r - c)) {
                    continue;
                }

                col.add(c);
                posDiag.add(r + c);
                negDiag.add(r - c);

                backtrack(r + 1);

                col.delete(c);
                posDiag.delete(r + c);
                negDiag.delete(r - c);
            }
        }

        backtrack(0);
        return res;
    }
}

Matchsticks to square

Pasted image 20251103102805.png

Partition to K equal sum subset