Tìm mảng con có tổng bằng M

[nudark1234 (Nguyen Luong)]

Cho mảng một chiều các số nguyên và một số nguyên M. Hãy tìm một mảng con sao cho tổng các phần tử trong mảng bằng M

Em chỉ xuất được các mảng con mà có các phần tử nối tiếp nhau ví dụ như 2 3 4 và 4 5với M = 9, còn với 1 3 5 thì em không biết xuất ạ.
Mọi người chỉnh code giúp em với ạ. em cảm ơn.

#include <iostream>
using namespace std; 

int main () { 
int sl; 
int a[100]; 
cout << "\n nhap so luong phan tu: "; 

cin >> sl; 
for (int i = 0;i<sl;i++) { 
   cout << "\n a["<<i<<"]= ";
   cin >> a[i]; 
}
int x; 
cout << "\n nhap x: "; 
cin >> x; 

for (int i = 0;i<sl;i++) { 
    for (int k=0;k<9999;k++) { 
    int s=0; 
       for (int j=i;j<sl-k;j++) { 
           s+= a[j]; 
	   }
	    if (s==x) {
		for (int j=i;j<sl-k;j++) { 
           cout << a[j] << " "; 
	   }
	   cout << "\n";
}
	}
}
 return 0; 
 
}

[rogp10]

@nudark1234

Em chỉ xuất được các mảng con mà có các phần tử nối tiếp nhau ví dụ như 2 3 4 và 4 5với M = 9, còn với 1 3 5 thì em không biết xuất ạ.

Bạn xác định lại là mảng con hay dãy con nhé. Cách giải khác nhau đấy.

[nudark1234 (Nguyen Luong)]

Nếu dùng dãy con thì viết code thế nào ạ?

[thanhtrung2314 (Trung Nguyen)]

toy example cho dễ nhé
a = {1, 3, 2} và M = 3
đặt temp = {} (empty)
dãy con có tổng bằng 3 thì có 3 trường hợp, có thể chứa số 1, có thể không chứa số 1, hoặc cả hai. Thế nên ta check hết 2 trường hợp
TH1: (không chứa số 1)
a = {3, 2}, M = 3
temp = {}
TH2: (chứa số 1)
a = {3, 2}, M = 3 - 1 = 2
temp = {1}
với TH1, ta tiếp tục phân tích như ban đầu ta lại được
TH1.1: (không chứa số 3)
a = {2}, M = 3
temp = {}
ở đây ta thấy dù tiếp theo ta có chứa số 2 vào dãy hay không chứa thì cũng đều không thỏa, end kết thúc
TH1.2: (chứa số 3)
a = {2}, M = 3 - 3 = 0
temp = {3}
lúc này, M = 0, ta ghi lại kết quả temp, return kết thúc TH này.
rôì cứ thế ta cứ phân tích thêm =)) thỏa thì ghi lại kết quả. Thế thôi

package main

import "fmt"

var result [][]int

func solve(a []int, M int, temp []int) {
    if M == 0 {
        result = append(result, temp)
        return
    }
    if len(a) == 0 {
        return
    }
    solve(a[1:], M, temp)
    temp = append(temp, a[0])
    solve(a[1:], M-a[0], temp)

}

func main() {
    a := []int{1, 3, 2}
    M := 3
    solve(a, M, []int{})
    for _, val := range result {
        fmt.Println(val)
    }
}

đây là code mình viết bằng golang, chạy khá ngon =))

[nudark1234 (Nguyen Luong)]

Cho em hỏi golang là gì vậy ạ

[rogp10]

Mới học C++ mà táng golang vào

[Uni (Dang Hoang Tuan)]

Golang là tên gọi khác của Go, 1 ngôn ngữ lập trình được tạo ra bởi mấy ông ở Google. Go về cơ bản là C++ phiên bản Lite, đã được lược bỏ 1 vài tính năng của C++ như tính giai thừa để dễ hiểu hơn.

[nudark1234 (Nguyen Luong)]

Vâng em cảm ơn, mà em không biết lite là gì ạ. anh giải thích dùm em được không

[nudark1234 (Nguyen Luong)]

Anh chỉ bài tìm dãy con theo đề bài trên bằng c++ được không ạ?

[Uni (Dang Hoang Tuan)]

1 thứ gì đó được gọi là Lite khi nó là phiên bản có size nhỏ hơn, ít tính năng hơn và đơn giản hơn so với phiên bản gốc. Mà mình gọi Go là C++ phiên bản Lite cũng không đúng lắm vì Go vẫn có 1 số tính năng độc nhất so với C++ và syntax của Go và C++ vẫn khác nhau.

[nudark1234 (Nguyen Luong)]

Okk anh, rất dễ hiểu luôn