MIN_SEG.cpp

#include <iostream>
#include <vector>

using namespace std;

struct Result
{
	int fromIndex, len;
	long long total;

	Result(int index, long long total, int len){
		this->fromIndex = index;
		this->total = total;
		this->len = len;
	}

};

struct Node{
	long long value;
	int index;
	vector<Result> results;

	Node(long long value, int index){
		this->value = value; 
		this->index = index;

	}

};

vector<Node> nodes;



int main()
{
	
	int n = 12;
	long long k = 10;

	long long arr[] = {2,1,5, 3, 2, 0, 9, 1, 0, 5, 0, 41};

	// Dua cac number vao mang vector gom cac Node
	for (int i = 0; i < n; ++i)
	{
		Node node(arr[i], i);
		nodes.push_back(node);

	}

	Result result(0, nodes[0].value, 1);
	nodes[0].results.push_back(result);

	Result minResult(-1, -1, 0);
	bool hasMinResult = false;

	for (int i = 1; i < nodes.size(); ++i)
	{
		
			Node lastNode = nodes[i-1];
			Node *currentNode = &nodes[i];

			for (int j = 0; j < lastNode.results.size(); ++j)
			{
					
					Result result = lastNode.results[j];

					result.total  += currentNode->value;
					result.len += 1;

					//cout << "Debug:" << result.total << " len:" << result.len; 

					if(result.total > k){
						continue;
					}

					if(result.total == k){
							if(hasMinResult){
								if(result.len < minResult.len){
									minResult = result;
								}

							}else{
								minResult = result;
								hasMinResult = true;
							}

					}

					currentNode->results.push_back(result);
			}

			// add current number result
			Result r(i, currentNode->value, 1);

			currentNode->results.push_back(r);


	}


		if(hasMinResult){

				cout <<  minResult.fromIndex +1 << " " << minResult.fromIndex + minResult.len;
 		}

	

	return 0;
}