6.2 Combinations, Permutations & Grid Backtracking

1. What Is the Difference Between Subsets, Combinations & Permutations?

Beginners often mix these three up. Here is the plain-English difference on [1, 2, 3]:

1. Subsets: Any group of any size where order does NOT matter ([], [1], [1, 2], ...).
2. Combinations: Groups that hit a specific size k or target sum where order does NOT matter ([1, 2] and [2, 1] count as the same combination).
3. Permutations: Every possible ordering of the items ([1, 2, 3], [1, 3, 2], [2, 1, 3], ... — N! total). Here [1, 2] and [2, 1] are different!

2. How Each Pattern Works in Code

Pattern A: Combinations (start Index Prevents Looking Backward)

To avoid generating both [2, 3] and [3, 2], pass a start index into dfs(start, remaining_target):

• If you can reuse the same number unlimited times (Combination Sum), recurse with dfs(i, rem - nums[i]).
• If you can use each element at most once (Combination Sum II), recurse with dfs(i + 1, rem - nums[i]).
• Duplicate Skipping Rule: If the input has duplicate numbers, sort first and add if i > start and nums[i] == nums[i - 1]: continue.

Pattern B: Permutations (used[] Boolean Array)

Because order matters, every recursive call loops i from 0 to n - 1, using a used[i] array so we don't pick the exact same index twice in the same arrangement.

Pattern C: 2D Grid Backtracking (Word Search & N-Queens)

When searching for a word on a 2D grid, step to (r+1, c), (r-1, c), (r, c+1), (r, c-1). Temporarily mark board[r][c] = '#' before recursing so your path doesn't step back onto the same square, and restore board[r][c] = original_char on the way back up!

3. Basic Operations & Walkthroughs (All 4 Languages)

# 1. Combination Sum (Unlimited reuse of candidates[i] -> pass i, not i + 1)
def combination_sum(candidates: list[int], target: int) -> list[list[int]]:
  res, path = [], []

  def dfs(start: int, rem: int) -> None:
      if rem == 0:
          res.append(path[:])
          return
      if rem < 0:
          return
      for i in range(start, len(candidates)):
          path.append(candidates[i])
          dfs(i, rem - candidates[i])
          path.pop()

  dfs(0, target)
  return res

# 2. Permutations (All N! orderings using used[] array)
def permute(nums: list[int]) -> list[list[int]]:
  res, path = [], []
  used = [False] * len(nums)

  def dfs() -> None:
      if len(path) == len(nums):
          res.append(path[:])
          return
      for i in range(len(nums)):
          if not used[i]:
              used[i] = True
              path.append(nums[i])
              dfs()
              path.pop()
              used[i] = False

  dfs()
  return res

4. Core Interview Patterns & Common Traps

# 2D Grid Backtracking (Word Search):
def dfs(r: int, c: int, k: int) -> bool:
  if k == len(word): return True
  if not (0 <= r < R and 0 <= c < C) or board[r][c] != word[k]:
      return False
  saved, board[r][c] = board[r][c], "#"  # 1. Mark visited
  found = any(dfs(r+dr, c+dc, k+1) for dr, dc in ((1,0),(-1,0),(0,1),(0,-1)))
  board[r][c] = saved                    # 2. Undo mark!
  return found

5. Practice On Your Own (Curated Submodule Problems)