Find print all subsets in an integer array

In this article, we explore how to find and print all possible subsets of an integer array using the backtracking technique in Python. Subsets are combinations of elements from the array that can be empty, contain a single element, or consist of multiple elements. We will implement a recursive backtracking function to generate these subsets efficiently. By following this approach, we can systematically explore all possible combinations and print them as output. Understanding how to find subsets of an array is essential for various problem-solving scenarios in computer science and data analysis.

def print_all_subsets(arr, target):
n = len(arr)

# Create a 2D table to store the subset sums
dp = [[False] * (target + 1) for _ in range(n + 1)]

# Initialize the first column as True (sum of 0 is possible)
for i in range(n + 1):
dp[i][0] = True

# Fill the table bottom-up
for i in range(1, n + 1):

for j in range(1, target + 1):

if j < arr[i - 1]:
dp[i][j] = dp[i - 1][j]
else:
dp[i][j] = dp[i - 1][j] or dp[i - 1][j - arr[i - 1]]

# Traverse the last row to find subsets with the target sum
subsets = []
def backtrack(i, current_sum, current_subset):

if i == 0 and current_sum == 0:
subsets.append(current_subset)
return
if i == 0 or current_sum < 0 or not dp[i][current_sum]:
return

# Exclude the current element
backtrack(i - 1, current_sum, current_subset)

# Include the current element
backtrack(i - 1, current_sum - arr[i - 1], [arr[i - 1]] + current_subset)

backtrack(n, target, [])

return subsets

usage

arr = [2, 4, 6, 3, 8, 5]
target = 10
result = print_all_subsets(arr, target)
for subset in result:
print(subset)

#Output

[4, 6]
[2, 8]
[2, 3, 5]