# 01.08.2023 [77. Combinations]

All combinations choosing `k` numbers from `1..n` numbers

01.08.2023

77. Combinations medium
blog post

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 } }