Given an array, return true if it can be partitioned into two subarrays whose sum of elements are the same, else return false. Example: Input: {5,1,5,11} Output: true (as it can be divided into {5,1,5} {11} where 5+1+5=11)

Question

Accepted Answer

Check if an array can be partitioned into two subarrays with equal sum.

Iterate through the array and calculate the total sum of all elements.
If the sum is odd, return false as it cannot be divided into two equal parts.
If the sum is even, try to find a subset with sum equal to half of the total sum.
Use dynamic programming or backtracking to find the subset sum.

Accepted Answer

def can_partition(arr):

total_sum = sum(arr)

if total_sum % 2 != 0:

return False

target_sum = total_sum // 2

n = len(arr)

dp = [[False] * (target_sum + 1) for _ in range(n+1)]

for i in range(n+1):

dp[i][0] = True

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

for j in range(1, target_sum+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]]

return dp[n][target_sum]

Given an array, return true if it can be partitioned into two subarrays whose sum of elements are the same, else return false. Example: Input: {5,1,5,11} Output: true (as it can be divided into {5,1,5} {11} where 5+1+5=11)

Housing.com Software Developer interview questions & answers

Popular interview questions of Software Developer