Answered: a | bartleby

Database System Concepts

7th Edition

ISBN:9780078022159

Author:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan

Publisher:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan

Chapter1: Introduction

Section: Chapter Questions

Problem 1PE

See similar textbooks

Related questions

Question

We will be looking at a problem known as the partition problem. The partition problem is to determine
if a given set can be partitioned into two subsets such that the sum of elements in both subsets is the
same. This is a variant of the 0-1 knapsack problem.

You would notice that the code only returns True or False. Suppose now you need to change the
code using Backtracking such that it returns the numbers of the subsets.
Please explain your codes.

# Returns true if there exists a sublist of list `nums[0…n)` with the given sum

def subsetSum(nums, total):

n = len(nums)

# `T[i][j]` stores true if subset with sum `j` can be attained

# using items up to first `i` items

T = [[False for x in range(total + 1)] for y in range(n + 1)]

# if the sum is zero

for i in range(n + 1):

T[i][0] = True

# do for i'th item

for i in range(1, n + 1):

# consider all sum from 1 to total

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

# don't include the i'th element if `j-nums[i-1]` is negative

if nums[i - 1] > j:

T[i][j] = T[i - 1][j]

else:

# find the subset with sum `j` by excluding or including the i'th item

T[i][j] = T[i - 1][j] or T[i - 1][j - nums[i - 1]]

# return maximum value

return T[n][total]

# Returns true if given list `nums[0…n-1]` can be divided into two

# sublists with equal sum

def partition(nums):

total = sum(nums)

# return true if the sum is even and the list can be divided into

# two sublists with equal sum

return (total & 1) == 0 and subsetSum(nums, total // 2)

if __name__ == '__main__':

# Input: a set of items

nums = [7, 3, 1, 5, 4, 8]

if partition(nums):

print('Set can be partitioned')

else:

print('Set cannot be partitioned')

Expert Solution

Step by step

Solved in 2 steps with 2 images

SEE SOLUTION Check out a sample Q&A here

Knowledge Booster

Learn more about

Need a deep-dive on the concept behind this application? Look no further. Learn more about this topic, computer-science and related others by exploring similar questions and additional content below.

Similar questions