LeetCode Entry

77. Combinations

01.08.2023 medium 2023 kotlin

All combinations choosing k numbers from 1..n numbers

77. Combinations medium blog post substack image.png

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/295

Problem TLDR

All combinations choosing k numbers from 1..n numbers

Intuition

As total number is 20, we can use bit mask to generate all possible 2^n bit masks, then choose only k 1-bits masks and generate lists.

Approach

Let’s write a Kotlin one-liner

Complexity

  • Time complexity: \(O(n2^n)\)

  • Space complexity: \(O(n2^n)\)

Code


    fun combine(n: Int, k: Int): List<List<Int>> = (0 until (1 shl n))
      .filter { Integer.bitCount(it) == k }
      .map { mask -> (1..n).filter { mask and (1 shl it - 1) != 0 } }