How to Distinguish Combination Problems from Permutation Problems in the LeetCode-Master Curriculum

Combination problems ignore element order and typically use a start index to avoid duplicates, while permutation problems treat different orders as distinct solutions and rely on swapping or used arrays to track selected elements.

The youngyangyang04/leetcode-master repository organizes backtracking algorithms into distinct categories based on whether the problem requires combinations or permutations. Understanding this distinction is essential for selecting the correct template and avoiding redundant computations in your solutions.

Core Distinction: Order and Reuse

Order Matters

In combination problems, the solution [1,2] is identical to [2,1]. The curriculum emphasizes that combinations represent "collections" where sequence is irrelevant. Conversely, permutation problems treat [1,2] and [2,1] as two distinct valid answers because permutations represent "arrangements" where every ordering matters.

Element Reuse Rules

The repository highlights that combination problems often include variants with specific reuse constraints:

• Standard combinations (e.g., subsets) disallow reusing the same element
• Combination Sum problems allow unlimited reuse of the same candidate number
• Combination Sum II allows each number to be used only once, even if duplicates exist in the input

Permutation problems typically prohibit element reuse unless explicitly stated (as in Permutations II), using a used array or in-place swapping to ensure each element appears exactly once in each arrangement.

Algorithmic Patterns in the Curriculum

Combination Pattern: Start Index and Pruning

The combination solutions in files like 0039.组合总和.md and 0040.组合总和II.md implement a depth-first search that passes a start parameter to enforce non-decreasing selection. This prevents generating [2,1] after [1,2] has already been recorded.

def combinationSum(candidates, target):
    res = []
    candidates.sort()
    
    def dfs(start, path, total):
        if total == target:
            res.append(path[:])
            return
        if total > target:
            return
        for i in range(start, len(candidates)):
            # reuse i because unlimited use is allowed

            dfs(i, path + [candidates[i]], total + candidates[i])
    
    dfs(0, [], 0)
    return res

The start index ensures that subsequent recursive calls only consider elements at or after the current position, eliminating permutations of the same combination.

Permutation Pattern: Swapping and Used Arrays

Files like 0046.全排列.md and 0047.全排列II.md demonstrate that permutations require tracking which elements have been placed in the current arrangement. The curriculum presents two approaches: maintaining a used boolean array or performing in-place swaps.

def permute(nums):
    res = []
    
    def backtrack(first=0):
        # all numbers are used

        if first == len(nums):
            res.append(nums[:])
            return
        for i in range(first, len(nums)):
            nums[first], nums[i] = nums[i], nums[first]   # place i-th element first

            backtrack(first + 1)
            nums[first], nums[i] = nums[i], nums[first]   # backtrack

    
    backtrack()
    return res

This swapping mechanism generates every possible ordering by systematically exchanging each element into the current position, then recursively solving for the remaining positions.

Key Repository Files

The leetcode-master curriculum organizes these concepts into specific markdown files that provide problem statements, complexity analysis, and reference implementations:

• Combination fundamentals: 0039.组合总和.md – introduces the start-index pattern with unlimited element reuse
• Combination with duplicates: 0040.组合总和II.md – extends the pattern to handle duplicate candidates while avoiding duplicate combinations
• Subset generation: 0078.子集.md – demonstrates how combination logic generates all subsets (the power set)
• Permutations: 0046.全排列.md – covers the basic swapping approach for generating all arrangements
• Permutations with duplicates: 0047.全排列II.md – adds pruning logic to handle duplicate elements in the input array
• Letter combinations: 0017.电话号码的字母组合.md – applies combination logic to Cartesian product scenarios

Summary

• Order sensitivity defines the boundary: combinations ignore sequence while permutations treat every ordering as unique
• Implementation patterns differ: combinations use a start index to enforce non-decreasing selection, whereas permutations use swapping or used arrays to track placed elements
• Reuse rules vary by problem: combination problems may allow unlimited or limited reuse (as in Combination Sum variants), while standard permutation problems prohibit reuse unless explicitly stated
• Repository structure: the leetcode-master curriculum separates these into distinct files that demonstrate the appropriate backtracking template for each category

Frequently Asked Questions

How do I know if a problem is a combination or permutation problem?

Examine whether the order of elements in the solution matters. If the problem asks for "subsets," "combinations," or "groups" where [1,2] equals [2,1], it is a combination problem. If it asks for "arrangements," "orderings," or "sequences" where [1,2] and [2,1] are different answers, it is a permutation problem.

Why does the combination pattern use a start index?

The start index ensures that each recursive call only considers elements at or after the current position in the input array. This prevents the algorithm from generating permutations of the same combination (like [1,2] and [2,1]) and guarantees that each valid combination is discovered exactly once in a non-decreasing order.

Can permutation problems allow duplicate elements?

Yes, but the implementation must handle them carefully to avoid generating duplicate permutations. In the leetcode-master repository, 0047.全排列II.md demonstrates sorting the input first, then using a used array or checking nums[i] == nums[i-1] with additional conditions to skip over duplicate values during the backtracking process.

Which pattern generates more solutions, combinations or permutations?

Permutations generate significantly more solutions. For a set of n distinct elements, there are n! (n factorial) permutations but only 2^n subsets (combinations of all sizes). When selecting k elements from n, permutations yield n!/(n-k)! arrangements while combinations yield only n!/(k!(n-k)!) groups. This exponential difference makes permutation problems more computationally expensive and requires more aggressive pruning strategies.

{
  "mcpServers": {
    "instagit": {
      "command": "npx",
      "args": ["-y", "instagit@latest"]
    }
  }
}