Question

How to find all possible combinations of numbers from a vector that equal to N in C++

Answer 1

#include <vector>
#include <iostream>
#include <sstream>  
#include <iterator>

void GetCombinationsEqualToN(std::vector<int> arr, int N, std::vector<int> combination) {
    int sum = 0;

    for (auto num : combination) {
	   sum += num;
    }

    if (sum == N) {
        std::stringstream ss;
        copy(combination.begin(), combination.end(), std::ostream_iterator<int>(ss, ", "));
        std::string str = ss.str();
        
	    std::cout << "sum(" << str << ") = " << N << "\n";
    }

    if (sum >= N) {
		return;
    }

    for (int i = 0; i < arr.size(); i++) {
		 std::vector<int> remaining;

		 for (int j = i + 1; j < arr.size(); j++) {
			 remaining.push_back(arr[j]);
		 }

		 std::vector<int> combination_next(combination);
		 combination_next.push_back(arr[i]);

		 GetCombinationsEqualToN(remaining, N, combination_next);
    }
}

int main(void)
{
	std::vector<int> v = {4, 6, 8, 2, 1, 10, 3, 5, 13};
	std::vector<int> combination; 
	int N = 13;
	
	GetCombinationsEqualToN(v, N, combination);
}




/*
run:

sum(4, 6, 2, 1, ) = 13
sum(4, 6, 3, ) = 13
sum(4, 8, 1, ) = 13
sum(4, 1, 3, 5, ) = 13
sum(6, 2, 5, ) = 13
sum(8, 2, 3, ) = 13
sum(8, 5, ) = 13
sum(2, 1, 10, ) = 13
sum(10, 3, ) = 13
sum(13, ) = 13

*/

 

70+ SQL courses for beginners and professionals