generating powerset with backtracking where subsets with lower number of elements appear earlier and they are sorted

Question

I was solving the classic powerset generation using backtracking. Now, let's say, I add another constraint, the output should appear in a specific order. For input = [1, 2, 3], the output should be [[], [1], [2], [3], [1,2], [1,3], [2,3], [1,2,3]]

My general solution (which generates the superset but not in any specific order):

class Solution:
    def build_subsets(self, cur_i = 0, cur_ls = []):
        if cur_i == len(self.nums):
            self.output.append(cur_ls)
            return # this is mendatory
            
        self.build_subsets(cur_i + 1, cur_ls)
        self.build_subsets(cur_i + 1, cur_ls + [self.nums[cur_i]])
        

    def subsets(self, nums):
        self.nums = nums
        self.output = []
        self.build_subsets()
        return self.output

How can I change my backtracking code to find the output in the specific order (subsets with a lower number of elements appear earlier and they are sorted [for a group of a fixed number of elements])?

Update: The following code which uses combinations function satisfy the condition. Now, the question becomes how can I write combinations using backtracking as I want to understand the recursive process for generating such a list.

from itertools import chain, combinations
def powerset(iterable):
    "powerset([1,2,3]) --> () (1,) (2,) (3,) (1,2) (1,3) (2,3) (1,2,3)"
    s = list(iterable)
    return chain.from_iterable(combinations(s, r) for r in range(len(s)+1))

Answer 1

Your code has almost everything you need to generate the subsets in the desired order. The key missing piece is the for loop that determines the length of the subsets, as seen in the code that uses combinations. That loop starts by generating the subsets of length 0. It then continues with successively larger subsets until it reaches the final subset that includes all of the numbers.

So you need to add a similar for loop to the subsets function, and the desired length needs to be passed to the build_subsets function. The build_subsets function then needs to terminate the recursion when the subset reaches the desired length.

Other changes that are needed are:

• The order of the recursive calls needs to be reversed so that the current number is used, before being skipped.
• When the current number is skipped, it's necessary to verify that enough numbers remain to complete the subset, before making the recursive call.

With those changes, the code looks like this:

class Solution:
    def build_subsets(self, desired_length, cur_i = 0, cur_ls = []):
        # if the current subset is the desired length, add it to the output
        if len(cur_ls) == desired_length:
            self.output.append(cur_ls)
            return

        # use the current number
        self.build_subsets(desired_length, cur_i+1, cur_ls + [self.nums[cur_i]]);

        # skip the current number, if there are enough numbers to finish the subset
        cur_i += 1
        if len(self.nums) - cur_i >= desired_length - len(cur_ls):
            self.build_subsets(desired_length, cur_i, cur_ls);

    def subsets(self, nums):
        self.nums = nums
        self.output = []
        for desired_length in range(len(nums)+1):
            self.build_subsets(desired_length)
        return self.output

Answer 2

the big picture

This solution hopes to teach you that complex problems can be made by combining solutions to smaller sub-problems. After all, this is often the way we should be thinking about recursive problems. Recursion is a functional heritage and so using it with functional style will yield the best results. This means avoiding things like mutation, variable reassignment, and other side effects.

def powerset(t):
  for k in range(len(t)):
    yield from combinations(t, k)
  yield t

for x in powerset((1,2,3)):
  print(x)

The combinations will be ordered in the same way the original input is ordered. If you would like the output to be sorted, simply sort the input first -

()
(1,)
(2,)
(3,)
(1, 2)
(1, 3)
(2, 3)
(1, 2, 3)

Since you asked how to write it, here is combinations as its own generic function -

def combinations(t, k):
  if k <= 0:
    yield ()
  elif not t:
    return
  else:
    for x in combinations(t[1:], k - 1):
      yield (t[0], *x)
    yield from combinations(t[1:], k)

itertools

Or you can use the built in itertools.combinations function, provided by python -

from itertools import combinations   # <- import

def powerset(t):
  for k in range(len(t)):
    yield from combinations(t, k)  # <- provided by python
  yield t

for x in powerset((3,2,1)):  # <- let's try a different input order
  print(x)

()
(3,)
(2,)
(1,)
(3, 2)
(3, 1)
(2, 1)
(3, 2, 1)

accept list as input

Notice above there's no need to "generate" the final subset as it is simply t itself. If you want to accept a list or non-tuple as an input, we can slightly alter powerset -

def powerset(t):
  for k in range(len(t)):
    yield from combinations(t, k)
  yield tuple(t)                    # <- coerce tuple

for x in powerset([9,3,6]):         # <- list input
  print(x) 

Before this change the program would output [9,3,6] instead of the desired (9,3,6) -

()
(9,)
(3,)
(6,)
(9, 3)
(9, 6)
(3, 6)
(9, 3, 6)

generators

Notice we use yield to lazily generate the possible subsets. Generators are a good fit for combinatorics problems because often times we do not need to iterate the entire solution space before an answer can be determined. This way the caller can work with the results ad hoc, as they are generated, without necessarily computing every subset.

Show all orders containing fries -

for order in powerset(""): # <- input can be a string too!
  if "" in order:
    print(order)

('',)
('', '')
('', '')
('', '', '')

Sometimes however you will want all of the results, and that's perfectly okay. The natural way to turn an iterable generator to a list is to use the list function -

print(list(powerset("")))

All of the possible orders are collected into a list now -

[(), ('',), ('',), ('',), ('', ''), ('', ''), ('', ''), ('', '', '')]

practice makes permanent

LeetCode (and other sites like it) provided exercises that will often start you with some boilerplate code to fill in -

class Solution:
  def subsets(self, nums):
    # implement the solution here

Writing code in the template sets you up for failure as it unnecessarily tangles your ordinary functions with self context and makes it difficult to reuse your code elsewhere. As beginners practice over and over, they begin to see this as the correct way to write code. It's not.

Instead write ordinary functions as we have above and simply call them in the awkward Solution class wrapper -

def combinations(...):
  ...

def powerset(...):
  ...

class Solution:
  def subsets(self, nums):
    return powerset(nums)  # <- call your function in the wrapper