Cho tổng, tìm các dãy số có tổng bằng tổng đã cho

#1

Em chào mọi người ạ, em đang có một bài toán thế này, mong mọi người cho em xin giải thuật với ạ.
Array = [1,3,5,8,4,2,10]
Cho tổng = 10
TimCacTH(array,10)
Bài toán tìm ra các trường hợp này ạ
1 + 3 + 4 + 2 = 10
1 + 5 + 4 = 10
3 + 5 + 2 = 10
8 + 2 = 10
10 = 10

Em ko biết viết vòng lặp sao cho cộng tất cả các trường hợp lại với nhau, em cám ơn mn ạ

#2

Ít phần tử thì quay lui.

Về bản chất ta đang duyệt các dãy nhị phân độ dài n. Giờ vẽ cây lựa chọn 0/1 cho mảng 4 phần tử thôi :smiley:

6 Likes
#3

Em chưa dc học cây nhị phân ạ

#4

bài toán không có scope rõ ràng nên không biết giải pháp nào cho đủ
còn chạy được thì cứ đệ quy (lấy/không lấy) kết hợp điều kiện dừng thôi

5 Likes
#5

Dạ yêu cầu chỉ cần đưa ra các dãy số duy nhất thoả mãn là dc anh ạ

#6

Cái cây để bạn hình dung quá trình quay lui ấy :smiley:

4 Likes
#7
  • Không biết đề còn cho thêm thông tin gì không, ví dụ như positive integer chẳng hạn?
2 Likes
#8

Bạn cứ chịu khó viết trên giấy , xog viết code thử , sai thì sữa lại rồi thử cái khác , dần sẽ quen . Đừng hỏi bài tập nó sẽ tạo thói quen xấu cho bạn

3 Likes
#9

Mình có ý tưởng thế này

Đặt L = [1, 3, 5, 8, 4, 2, 10], ta có số phần tử của L là 7.

for i từ 1 -> 7
	- Ở mỗi giá trị `i` ta tìm tất cả các tập hợp con có `i` phần từ của L (1).
	- Gọi tập con đó là LS
	for e in LS
		tính tổng của e, nếu nó = 10 thì in ra kết quả (2)

Ở chỗ (1) lưu ý các hoán vị, ví dụ [1, 2, 3] và [3, 2, 1] là như nhau. Nếu không thì ở bước (2) sort cái e rồi thêm nó vào Set, chạy xong in phần tử trong Set ra là được hoặc có thể vừa kiểm tra vừa in.

P/s. Làm sao để canh giữa ảnh vậy các bạn :sweat_smile:

1 Like
#10

Bạn nên hỏi làm sao để viết latex được vậy thì hơn. :smiley:

L := [1, 3, 5, 8, 4, 2, 10]\\ n := 7\\ \{[10]\}\\ \{[2, 8]\}\\ \{[1, 4, 5], [2, 3, 5]\}\\ \{[1, 2, 3, 4]\}

Vô đây xem cách dùng nhé. :slightly_smiling_face:

Chỉ cần duyệt tất cả các tập con là đủ hết trường hợp rồi, không cần tốn công sort đâu. :V :V
Mà nếu đề cho dãy toàn số dương thì có thế áp dụng thêm kỹ thuật nhánh cận. :slightly_smiling_face:

5 Likes
#11

Có số âm thì phức tạp hơn chút thôi :slight_smile: tại vì vẫn có minsum và maxsum.

S_{max} := \sum_{a > 0}^{a \in A} \ a\\\ \\ S_{min} := \sum_{a < 0}^{a \in A}\ a
5 Likes
#13

Bạn @Sherly1001 dùng Latex nha, không phải ảnh. Bình thường ảnh sẽ tự động căn giữa nếu đủ rộng, trường hợp ảnh không đủ rộng mà muốn căn giữa ảnh thì phải dùng HTML (cách hay dùng) hoặc BBCode.

Tìm hiểu thêm ở đây:

P/s: Hình như cái này off-topic rồi thì phải :thinking: ?

4 Likes
#14

Cám ơn bác ạ, mấy hôm em off mất nay vào đã có câu tl

83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?