Using Bitmasking Algorithm to Compute the Combinations of an Arr
- Time:2020-09-07 12:13:31
- Class:Weblog
- Read:26
Given two integers n and k, return all possible combinations of k numbers out of 1 … n.
Example:
Input: n = 4, k = 2 Output: [ [2,4], [3,4], [2,3], [1,2], [1,3], [1,4], ]
Combination Algorithm using Bitmasking
The combination can also be done in Recursive backtracking. However, it can also be implemented using the Bitmasking algorithm.
The idea is to bruteforce all possible configurations (of bitmasks) in O(2^N) where N is the length of the given input set. Then once the configuration has k bit sets, we output the corresponding configuration.
The following is the Python combination implementation using bitmasking.
1 2 3 4 5 6 7 8 9 10 11 | class Solution: def combine(self, n: int, k: int) -> List[List[int]]: ans = [] for b in (range(1 << n)): if bin(b).count('1') == k: cur = [] for i in range(n): if (b & (1 << i)) > 0: cur.append(i + 1) ans.append(cur) return ans |
class Solution: def combine(self, n: int, k: int) -> List[List[int]]: ans = [] for b in (range(1 << n)): if bin(b).count('1') == k: cur = [] for i in range(n): if (b & (1 << i)) > 0: cur.append(i + 1) ans.append(cur) return ans
and with slight changes – reversing the bit searching – still works
1 2 3 4 5 6 7 8 9 10 11 | class Solution: def combine(self, n: int, k: int) -> List[List[int]]: ans = [] for b in reversed(range(1 << n)): if bin(b).count('1') == k: cur = [] for i in range(n): if (b & (1 << (n - i - 1))) > 0: cur.append(i + 1) ans.append(cur) return ans |
class Solution: def combine(self, n: int, k: int) -> List[List[int]]: ans = [] for b in reversed(range(1 << n)): if bin(b).count('1') == k: cur = [] for i in range(n): if (b & (1 << (n - i - 1))) > 0: cur.append(i + 1) ans.append(cur) return ans
The recursive algorithm in C++: Recursive Combination Algorithm Implementation in C++.
Also, another interesting read: combination
–EOF (The Ultimate Computing & Technology Blog) —
Recommend:Compute the Indices of the Target Element in Array/List using Py
5 Cognitive Biases You Can Use to Boost E-Commerce Conversions
Important SEO Tips for E-commerce That You Cannot Disregard
5 Effective Ways to Improve Blog Conversion Rate
7 Reasons Blogging is Essential for Law Firms
Should Your Blog Extend Into Multimedia Forms of Content?
How Small Companies Can Use Big Data
Hands Up and Step Slowly Away from the Keyboard: Why Good Execut
How to Improve Bad Blog Posts
5 Things That Bloggers Use in Their Craft
- Comment list
-
- Comment add