Purva09/algorithm-battlefield

1"""Subset Generation Algorithms"""2 3from itertools import combinations4 5 6def subset_bitmasking(arr):7    """Subset Generation using Bitmasking"""8    n = len(arr)9    subsets = []10    11    for i in range(1 << n):  # 2^n combinations12        subset = []13        for j in range(n):14            if i & (1 << j):  # Check if j-th bit is set15                subset.append(arr[j])16        subsets.append(subset)17    18    return subsets19 20 21def subset_backtracking(arr, index=0, current=None, result=None):22    """Subset Generation using Backtracking"""23    if current is None:24        current = []25    if result is None:26        result = []27    28    result.append(current[:])29    30    for i in range(index, len(arr)):31        current.append(arr[i])32        subset_backtracking(arr, i + 1, current, result)33        current.pop()34    35    return result36 37 38def subset_recursive(arr):39    """Subset Generation using Recursion"""40    if len(arr) == 0:41        return [[]]42    43    first = arr[0]44    rest = arr[1:]45    rest_subsets = subset_recursive(rest)46    47    result = rest_subsets[:]48    for subset in rest_subsets:49        result.append([first] + subset)50    51    return result52 53 54def subset_iterative(arr):55    """Subset Generation using Iteration"""56    subsets = [[]]57    58    for elem in arr:59        subsets += [subset + [elem] for subset in subsets]60    61    return subsets62 63 64def subset_builtin(arr):65    """Subset Generation using Python Built-in Functions"""66    subsets = [[]]67    68    for i in range(1, len(arr) + 1):69        for combo in combinations(arr, i):70            subsets.append(list(combo))71    72    return subsets73