Katkat
Back

Generate combinations and permutations

ByteDanceSite Reliability Engineer · Technical Screen
MediumSite Reliability EngineerTechnical ScreenCoding & Algorithms

Last updated

This problem tests your ability to implement recursive backtracking algorithms to generate all possible permutations and combinations of a given set of distinct integers.

Problem Description

Given a collection of n distinct integers, implement two separate functions:

  1. get_permutations(nums): Return all possible permutations of the list.
  2. get_combinations(nums, k): Return all possible combinations of length k from the list.

Constraints

  • 1 <= len(nums) <= 8
  • Elements in nums are distinct.
  • 0 <= k <= len(nums)

Examples

Example 1: Permutations

input: nums = [1, 2]
output: [[1, 2], [2, 1]]

Example 2: Combinations

input: nums = [1, 2, 3], k = 2
output: [[1, 2], [1, 3], [2, 3]]

Edge Cases

  • What should the function return if k is 0?
  • How does the recursion handle an empty list vs. a single-element list?

Function Signatures

def get_permutations(nums: list[int]) -> list[list[int]]:
    pass

def get_combinations(nums: list[int], k: int) -> list[list[int]]:
    pass

Hints

Hint 1

For permutations, use a 'used' array or a set to keep track of which elements have already been placed in the current path.

Hint 2

For combinations, maintain an index pointer to ensure you only pick elements appearing after the current element in the list, avoiding duplicates like [1, 2] and [2, 1].

Hint 3

Both problems are classic applications of backtracking; focus on defining the 'base case' (when the path length reaches the target size) and the 'recursive step' (iterating through remaining candidates).

Follow-up questions

  • How would your approach change if the input list contained duplicate numbers (e.g., [1, 1, 2]) and you were required to return only unique permutations?
  • What is the time complexity of generating all permutations of length n? Is there a way to generate them iteratively rather than recursively?
  • If the input list size increased to 20, would it be feasible to return all permutations? Why or why not?