พาร์ติชันเท่ากับผลรวมย่อย (DP- 15) - อาร์เรย์ - บทช่วยสอน (2023)

#include โดยใช้เนมสเปซ std;bool subsetSumUtil(int ind, int target, vector& arr, vector> &dp){ if(target==0) return true; ถ้า (ind == 0) กลับ arr[0] == เป้าหมาย; if(dp[ind][target]!=-1) ส่งคืน dp[ind][target]; บูล notTaken = subsetSumUtil(ind-1,target,arr,dp); บูล = เท็จ; ถ้า(arr[ind]<=target) Take = subsetSumUtil(ind-1,target-arr[ind],arr,dp); ส่งคืน dp[ind][target]= notTaken||taken;}bool canPartition(int n, vector &arr){ int totSum=0; สำหรับ (int i=0; i> dp(n,เวกเตอร์(k+1,-1)); ส่งคืน subsetSumUtil(n-1,k,arr,dp); } }int main() { เวกเตอร์ arr = {2,3,3,3,4,5}; int n = arr.size(); if(canPartition(n,arr)) cout<<"อาร์เรย์สามารถแบ่งพาร์ติชันออกเป็นสองส่วนย่อยเท่าๆ กัน"; ศาลอื่น<<"อาร์เรย์ไม่สามารถแบ่งพาร์ติชันออกเป็นสองส่วนย่อยเท่าๆ กัน";}

เอาท์พุต:

อาร์เรย์สามารถแบ่งพาร์ติชันออกเป็นสองส่วนย่อยเท่าๆ กัน

ความซับซ้อนของเวลา: O(N*K) + O(N)

เหตุผล: มีสถานะ N*K ดังนั้นเมื่อสูงสุด 'N*K' ปัญหาใหม่จะได้รับการแก้ไข และเรากำลังเรียกใช้ for loop สำหรับ 'N' ครั้งเพื่อคำนวณผลรวมทั้งหมด

ความซับซ้อนของอวกาศ: O(N*K) + O(N)

เหตุผล: เรากำลังใช้ recursion stack space(O(N)) และ 2D array ( O(N*K))

นำเข้า java.util.*;class TUF{static boolean subsetSumUtil(int ind, int target,int arr[],int[][] dp){ if(target==0) return true; ถ้า (ind == 0) กลับ arr[0] == เป้าหมาย; if(dp[ind][target]!=-1) ส่งคืน dp[ind][target]==0?false:true; บูลีน notTaken = subsetSumUtil(ind-1,target,arr,dp); บูลีนถ่าย = เท็จ; ถ้า(arr[ind]<=target) Take = subsetSumUtil(ind-1,target-arr[ind],arr,dp); dp[ind][target]=ไม่ถ่าย||ถ่ายแล้ว?1:0; กลับ notTaken||taken;}บูลีนคงที่ canPartition(int n,int[] arr){ int totSum=0; สำหรับ (int i=0; i

เอาท์พุต:

อาร์เรย์สามารถแบ่งพาร์ติชันออกเป็นสองส่วนย่อยเท่าๆ กัน

ความซับซ้อนของเวลา: O(N*K) + O(N)

เหตุผล: มีสถานะ N*K ดังนั้นเมื่อสูงสุด 'N*K' ปัญหาใหม่จะได้รับการแก้ไข และเรากำลังเรียกใช้ for loop สำหรับ 'N' ครั้งเพื่อคำนวณผลรวมทั้งหมด

ความซับซ้อนของอวกาศ: O(N*K) + O(N)

เหตุผล: เรากำลังใช้ recursion stack space(O(N)) และ 2D array ( O(N*K))

def subsetSumUtil(ind, target, arr, dp): if target == 0: return True ถ้า ind == 0: return arr[0] == target if dp[ind][target] != -1: return dp[ ind][target] notTaken = subsetSumUtil(ind-1, target, arr, dp) Taken = False if arr[ind] <= target: Taken = subsetSumUtil(ind-1, target-arr[ind], arr, dp) dp[ind][target] = notTaken หรือ Take return dp[ind][target]def canPartition(n, arr): totSum = sum(arr) if totSum % 2 == 1: return False else: k = totSum // 2 dp = [[-1 for i in range(k+1)] for j in range(n)] return subsetSumUtil(n-1, k, arr, dp)def main(): arr = [2, 3, 3, 3, 4, 5] n = len(arr) if canPartition(n, arr): พิมพ์("อาร์เรย์สามารถแบ่งพาร์ติชันออกเป็นสองส่วนย่อยเท่าๆ กัน") อื่น: พิมพ์("ไม่สามารถแบ่งอาร์เรย์ออกเป็นสองส่วนย่อยเท่าๆ กัน ") ถ้า __name__ == "__main__": main()

เอาท์พุต:

อาร์เรย์สามารถแบ่งพาร์ติชันออกเป็นสองส่วนย่อยเท่าๆ กัน

ความซับซ้อนของเวลา: O(N*K) + O(N)

เหตุผล: มีสถานะ N*K ดังนั้นเมื่อสูงสุด 'N*K' ปัญหาใหม่จะได้รับการแก้ไข และเรากำลังเรียกใช้ for loop สำหรับ 'N' ครั้งเพื่อคำนวณผลรวมทั้งหมด

ความซับซ้อนของอวกาศ: O(N*K) + O(N)

เหตุผล: เรากำลังใช้ recursion stack space(O(N)) และ 2D array ( O(N*K))

#include โดยใช้เนมสเปซ std;bool canPartition(int n, vector &arr){ int totSum=0; สำหรับ (int i=0; i> dp(n,เวกเตอร์<บูล>(k+1,เท็จ)); สำหรับ (int i=0; i arr = {2,3,3,3,4,5}; int n = arr.size(); if(canPartition(n,arr)) cout<<"อาร์เรย์สามารถแบ่งพาร์ติชันออกเป็นสองส่วนย่อยเท่าๆ กัน"; ศาลอื่น<<"อาร์เรย์ไม่สามารถแบ่งพาร์ติชันออกเป็นสองส่วนย่อยเท่าๆ กัน";}

เอาท์พุต:

อาร์เรย์สามารถแบ่งพาร์ติชันออกเป็นสองส่วนย่อยเท่าๆ กัน

ความซับซ้อนของเวลา: O(N*K) +O(N)

เหตุผล: มีลูปที่ซ้อนกันสองลูปที่อธิบาย O(N*K) และเมื่อเริ่มต้น เรากำลังเรียกใช้ for ลูปเพื่อคำนวณ totSum

ความซับซ้อนของอวกาศ: O(N*K)

เหตุผล: เรากำลังใช้อาร์เรย์ภายนอกขนาด 'N*K' Stack Space ถูกกำจัด

นำเข้า java.util.*;class TUF{static boolean canPartition(int n,int[] arr){ int totSum=0; สำหรับ (int i=0; i

เอาท์พุต:

อาร์เรย์สามารถแบ่งพาร์ติชันออกเป็นสองส่วนย่อยเท่าๆ กัน

ความซับซ้อนของเวลา: O(N*K) +O(N)

เหตุผล: มีลูปที่ซ้อนกันสองลูปที่อธิบาย O(N*K) และเมื่อเริ่มต้น เรากำลังเรียกใช้ for ลูปเพื่อคำนวณ totSum

ความซับซ้อนของอวกาศ: O(N*K)

เหตุผล: เรากำลังใช้อาร์เรย์ภายนอกขนาด 'N*K' Stack Space ถูกกำจัด

def canPartition(n, arr): totSum = sum(arr) if totSum % 2 == 1: return False else: k = totSum // 2 dp = [[False for j in range(k + 1)] for i in range(n)] for i in range(n): dp[i][0] = True if arr[0] <= k: dp[0][arr[0]] = True for ind in range(1, n): สำหรับเป้าหมายในระยะ (1, k + 1): notTaken = dp[ind - 1][target] Taken = False if arr[ind] <= target: Taken = dp[ind - 1][target - arr [ind]] dp[ind][target] = ไม่ถ่ายหรือรับคืน dp[n - 1][k]def main(): arr = [2,3,3,3,4,5] n = len(arr ) if canPartition(n, arr): print("อาร์เรย์สามารถแบ่งพาร์ติชันออกเป็นสองส่วนย่อยเท่าๆ กัน") อื่น: พิมพ์("อาร์เรย์ไม่สามารถแบ่งพาร์ติชันออกเป็นสองส่วนย่อยเท่าๆ กัน")if __name__ == '__main__': main()

เอาท์พุต:

อาร์เรย์สามารถแบ่งพาร์ติชันออกเป็นสองส่วนย่อยเท่าๆ กัน

ความซับซ้อนของเวลา: O(N*K) +O(N)

เหตุผล: มีลูปที่ซ้อนกันสองลูปที่อธิบาย O(N*K) และเมื่อเริ่มต้น เรากำลังเรียกใช้ for ลูปเพื่อคำนวณ totSum

ความซับซ้อนของอวกาศ: O(N*K)

เหตุผล: เรากำลังใช้อาร์เรย์ภายนอกขนาด 'N*K' Stack Space ถูกกำจัด

#include โดยใช้เนมสเปซ std;bool canPartition(int n, vector &arr){ int totSum=0; สำหรับ (int i=0; i ก่อนหน้า (k+1,เท็จ); ก่อนหน้า[0] = จริง; ถ้า(arr[0]<=k) ก่อนหน้า[arr[0]] = จริง; สำหรับ (int ind = 1; ind cur(k+1,false); เคอร์[0] = จริง; สำหรับ (int target= 1; target<=k; target++){ บูล notTaken = ก่อนหน้า[เป้าหมาย]; บูล = เท็จ; ถ้า(arr[ind]<=target) Take = ก่อนหน้า[target-arr[ind]]; cur[target]= ไม่ถ่าย||ถ่ายแล้ว; } ก่อนหน้า = เคอร์; } กลับก่อนหน้า [k]; } }int main() { เวกเตอร์ arr = {2,3,3,3,4,5}; int n = arr.size(); if(canPartition(n,arr)) cout<<"อาร์เรย์สามารถแบ่งพาร์ติชันออกเป็นสองส่วนย่อยเท่าๆ กัน"; ศาลอื่น<<"อาร์เรย์ไม่สามารถแบ่งพาร์ติชันออกเป็นสองส่วนย่อยเท่าๆ กัน";}

เอาท์พุต:

Array สามารถแบ่งออกเป็นสองส่วนย่อยเท่า ๆ กัน

ความซับซ้อนของเวลา: O(N*K) +O(N)

เหตุผล: มีลูปที่ซ้อนกันสองลูปที่อธิบาย O(N*K) และเมื่อเริ่มต้น เรากำลังเรียกใช้ for ลูปเพื่อคำนวณ totSum

ความซับซ้อนของอวกาศ: O(K)

เหตุผล: เรากำลังใช้อาร์เรย์ภายนอกขนาด 'K+1' เพื่อจัดเก็บเพียงแถวเดียว

นำเข้า java.util.*;class TUF{static boolean canPartition(int n,int[] arr){ int totSum=0; สำหรับ (int i=0; i

เอาท์พุต:

Array สามารถแบ่งออกเป็นสองส่วนย่อยเท่า ๆ กัน

ความซับซ้อนของเวลา: O(N*K) +O(N)

เหตุผล: มีลูปที่ซ้อนกันสองลูปที่อธิบาย O(N*K) และเมื่อเริ่มต้น เรากำลังเรียกใช้ for ลูปเพื่อคำนวณ totSum

ความซับซ้อนของอวกาศ: O(K)

เหตุผล: เรากำลังใช้อาร์เรย์ภายนอกขนาด 'K+1' เพื่อจัดเก็บเพียงแถวเดียว

def canPartition(n, arr): totSum = sum(arr) if totSum % 2 == 1: return False else: k = totSum // 2 prev = [False] * (k + 1) prev[0] = True if arr[0] <= k: ก่อนหน้า[arr[0]] = True สำหรับ ind in range(1, n): cur = [False] * (k + 1) cur[0] = True สำหรับเป้าหมายในช่วง(1 , k + 1): notTaken = ก่อนหน้า[เป้าหมาย] ถ่าย = False ถ้า arr[ind] <= เป้าหมาย: ถ่าย = ก่อนหน้า[เป้าหมาย - arr[ind]] cur[target] = ไม่ถ่ายหรือถ่ายก่อนหน้า = เคอร์ส่งคืนค่าก่อนหน้า[k ]def main(): arr = [2, 3, 3, 3, 4, 5] n = len(arr) if canPartition(n, arr): print("อาร์เรย์สามารถแบ่งพาร์ติชันออกเป็นสองส่วนย่อยเท่าๆ กัน") อื่น : พิมพ์ ("ไม่สามารถแบ่งอาร์เรย์ออกเป็นสองส่วนย่อยเท่า ๆ กัน")if __name__ == "__main__": main()

เอาท์พุต:

Array สามารถแบ่งออกเป็นสองส่วนย่อยเท่า ๆ กัน

ความซับซ้อนของเวลา: O(N*K) +O(N)

เหตุผล: มีลูปที่ซ้อนกันสองลูปที่อธิบาย O(N*K) และเมื่อเริ่มต้น เรากำลังเรียกใช้ for ลูปเพื่อคำนวณ totSum

ความซับซ้อนของอวกาศ: O(K)

เหตุผล: เรากำลังใช้อาร์เรย์ภายนอกขนาด 'K+1' เพื่อจัดเก็บเพียงแถวเดียว