Subsets and Permutations: One Backtracking Template for Both

Author: 3d0eb07887

01 November 2026

Views: 7

Subsets, permutations, and combinations are the same backtracking skeleton with small changes. Learn the template once.

Subsets: at each index, choose to include or skip the element. Or loop from a start index, add the current path to the result, and recurse with start = i + 1. There are 2^n results.

Permutations: loop over all elements, skip ones already used (a boolean array), and add the path when its length is n. There are n! results.

Combinations of size k: the subsets loop, but only record paths of length k, and stop early when not enough elements remain.

Duplicates in the input: sort first, then skip nums[i] when it equals nums[i-1] at the same recursion depth (and, for permutations, when the previous duplicate is unused).

Complexity: always state it as output size times copying cost, for example O(n * 2^n) for subsets.

Practice tool I work on: https://www.linkjob.ai/

*Disclosure: I work on Linkjob AI.*


Edit Code:

Please enter an edit code

Edit codes must be at least 20 characters

Share