Tìm các tổng mà một mảng có thể được chia thành các mảng con có tổng bằng nhau trong Python

Giả sử chúng ta có một mảng các số nguyên A; chúng ta phải tìm tất cả các giá trị của tổng để với một giá trị sum [i] mảng có thể được chia thành các mảng con của tổng tổng [i]. Nếu chúng ta không thể chia mảng thành các mảng con có tổng bằng nhau thì trả về -1.

Vì vậy, nếu đầu vào là A =[2, 4, 2, 2, 2, 4, 2, 6], thì đầu ra sẽ là [6,8,12] vì mảng có thể được chia thành các mảng con của tổng 6, 8 và 12. Các giá trị này như sau:[{2, 4}, {2, 2, 2}, {4, 2}, {6}] [{2, 4, 2}, {2, 2 , 4}, {2, 6}] [{2, 4, 2, 2, 2}, {4, 2, 6

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• n:=kích thước của một

• table:=một mảng có kích thước n và được lấp đầy bởi 0

• bảng [0]:=a [0]

• đối với tôi trong phạm vi từ 1 đến n, hãy thực hiện

  • bảng [i]:=a [i] + bảng [i - 1]

• S:=table [n - 1]

• my_map:=một bản đồ mới

• đối với tôi trong phạm vi từ 0 đến n, hãy thực hiện

  • my_map [table [i]]:=1

• answer:=một tập hợp mới

• đối với tôi trong phạm vi từ 1 đến phần nguyên của (căn bậc hai của (S)) + 1, thực hiện

  • nếu S mod i giống 0, thì

    • is_present:=True

    • part_1:=i

    • part_2:=thương số của S / i

    • đối với j trong phạm vi part_1 đến S + 1, hãy cập nhật từng bước theo part_1, thực hiện

      • nếu j không có trong my_map, thì

        • is_present:=Sai

        • đi ra từ vòng lặp

    • nếu is_present là true và part_1 không giống với S, thì

      • thêm (part_1) câu trả lời

    • is_present:=True

    • cho j trong phạm vi thương số từ (S / i) đến S + 1, cập nhật từng bước theo S // i, thực hiện

      • nếu j không có trong my_map, thì

        • is_present:=Sai;

        • đi ra từ vòng lặp

    • nếu is_present và part_2 không giống với S, thì

      • thêm (phần_2) câu trả lời

• nếu kích thước của câu trả lời bằng 0, thì

  • trả về -1

• trả lại câu trả lời

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

from math import sqrt
def find_sum(a) :
   n = len(a)
   table = [0] * n
   table[0] = a[0]
   for i in range(1, n) :
      table[i] = a[i] + table[i - 1]
   S = table[n - 1]
   my_map = {}
   for i in range(n) :
      my_map[table[i]] = 1
   answer = set()
   for i in range(1, int(sqrt(S)) + 1) :
      if (S % i == 0) :
         is_present = True;
         part_1 = i
         part_2 = S // i
         for j in range(part_1 , S + 1, part_1) :
            if j not in my_map :
               is_present = False
               break
         if (is_present and part_1 != S) :
            answer.add(part_1)
         is_present = True
         for j in range(S // i , S + 1 , S // i) :
            if j not in my_map:
               is_present = False;
               break
         if (is_present and part_2 != S) :
            answer.add(part_2)
   if(len(answer) == 0) :
      return -1
   return answer
a = [2, 4, 2, 2, 2, 4, 2, 6]
print(find_sum(a))

Đầu vào

[2, 4, 2, 2, 2, 4, 2, 6]

Đầu ra

{8, 12, 6}