generating powerset with backtracking where subsets with lower number of elements appear earlier and-CodePudding

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

CodePudding user response：

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