A function to check if any combination of numbers in the vector will contain up to int?
To begin with, I'm looking for something simple and easy to understand, not the most effective.
I am trying to create a function that will take the value vector
and int
. This function should return true
if any numbers in the vector can contain up to int.
The vector will start with numbers 1,2,3,4,5,6,7,8,9,10
in it and all program numbers will be deleted. There will be no duplicate numbers.
int
can be any number between 2 and 12.
Some examples:
- Function
-
vector = { 2,3,4,5 } int = 7;
returnstrue
because3 + 4 = 7
. Function -
vector = { 1,5,8 } int = 7;
returnsfalse
because none of those numbers can add to 7. Function -
vector = { 3,6 } int = 3;
returnstrue
because3 = 3
. Function -
vector = { 5 } int = 2;
returnsfalse
because five cannot add to two.
This is the very last feature that I need to finish the game I'm working on. I feel like I'm missing a simple solution, but I'm not sure. Can someone show me how to do this, or point me in the right direction on how to solve this problem? Thank you in advance.
source to share
Given the additional information in the comments, the following function should be executed (I assume the same number cannot be used twice in the sum):
typedef std::vector<int>::iterator iter;
bool contains_sum(iter begin, iter end, int sum)
{
while (begin != end)
{
--end;
if (*end > sum)
continue;
if (contains_sum(begin, end, sum - *end))
return true;
}
return sum == 0;
}
source to share
What you need to do is find all the possible combinations and then check if any of them have the correct amount. A double recursive function can check.
bool canFormSum(vector<int>::iterator rest, vector<int>::iterator end,
int sumSoFar, int targetSum)
{
if(rest == end) return false;
if(sumSoFar + *rest == targetSum) return true;
if(canFormSum(rest + 1, end, sumSoFar, targetSum)) return true;
if(sumSoFar + *rest > targetSum) return false;
return canFormSum(rest + 1, end, sumSoFar + *rest, targetSum);
}
This is a good example of recursive computation - but for anything other than small vectors, it has terrible performance.
source to share
For general cases (vector size> 10),
Let f({a, b, c, d, ...}, e)
be the result of whether any number in the set {a, b, c, d, ...}
is equal e
.
Note that if e = x + y + z + ...
, then either (1) a
is in the set {x, y, z, ...}
or (2) is a
not in the set {x, y, z, ...}
. This means that we have a recursive definition :
f({a, etc...}, e) = f({etc...}, e-a) || f({etc...}, e)
And, obviously, if the sum is 0, the ratio is always true, excluding any element from the set:
f({...}, 0) = true
and if the set is empty and the sum is nonzero, the ratio is always wrong:
f({}, e) = false (if e != 0)
These are basic recursion cases .
Edit: See also Subset Sum Problem for further discussion.
source to share
You should try every possible combination until you find a solution. SUch problems would be good for a prologue language. Therefore, we have to simulate backtracking. this code at the end of c.
#include<stdio.h>
int check (int* in, int sum) {
while (1) {
int act = *in++;
if (act == 0) return 0;
int rest = sum - act;
if (rest > 0) { // test in the order of expected likelyhoods
if (1 == check (in, rest)) return 1; // found
}
// if (rest < 0) return 0; // minor optimization, valid if list is ordered ascendant
if (rest == 0) return 1; // found;
}
//return -1; // only necessary on poor compilers
}
void pr (int* in, int sum) {
int res = check (in, sum);
while (*in) {
printf ("%d ", *in ++);
}
if (res == 0) {
printf(" != %d\n", sum);
} else {
printf(" == %d\n", sum);
}
}
int main () {
int p1[] = {2,3,4,5, 0};
pr (p1, 7);
int p2[] = {1,5,8, 0};
pr (p2, 7);
int p3[] = {3,6, 0};
pr (p3, 3);
int p4[] = {5, 0};
pr (p4, 2);
int p5[] = {1, 100, 6, 0};
pr (p5, 7);
return 0;
}
tested for launch
2 3 4 5 == 7
1 5 8 != 7
3 6 == 3
5 != 2
1 100 6 == 7
source to share
Just to compare my (C) solution with celtschk (C ++). (Basically comparing approach, not languages)
#include <iostream>
#include <vector>
using namespace std;
int counter = 0;
typedef std::vector<int>::iterator iter;
bool contains_sum(iter begin, iter end, int sum)
{
counter ++;
while (begin != end)
{
--end;
if (contains_sum(begin, end, sum - *end))
return true;
}
return sum == 0;
}
int main () {
vector<int> data;
for (int i = 1; i <= 30; i ++) {
data.push_back(i);
}
int target = 77;
if (contains_sum (data.begin(), data.end(), target)) {
cout << "possible\n" << counter;
} else {
cout << "not possible\n << counter";
}
}
output
possible
268304387
Means about 270 million calls of the recursive method
Now my approach
#include<stdio.h>
#include<stdlib.h>
int counter;
int check (int* in, int sum) {
counter ++;
while (1) {
int act = *in++;
if (act == 0) return 0;
int rest = sum - act;
if (rest == 0) return 1; // found;
if (rest > 0) {
if (1 == check (in, rest)) return 1; // found
}
}
return -1;
}
void pr (int* in, int sum) {
counter = 0;
int res = check (in, sum);
while (*in) {
printf ("%d ", *in ++);
}
if (res == 0) {
printf(" != %d %d\n", sum, counter);
} else {
printf(" == %d %d\n", sum, counter);
}
}
int main () {
int p0[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9,10,
11,12,13,14,15,16,17,18,19,20,
21,22,23,24,25,26,27,28,29,30,
0};
pr (p0, 77);
int p1[] = {2,3,4,5, 0};
pr (p1, 7);
int p2[] = {1,5,8, 0};
pr (p2, 7);
int p3[] = {3,6, 0};
pr (p3, 3);
int p4[] = {5, 0};
pr (p4, 2);
int p5[] = {1, 100, 6, 0};
pr (p5, 7);
return 0;
}
and this is the conclusion
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
20 21 22 23 24 25 26 27 28 29 30 == 77 22
2 3 4 5 == 7 4
1 5 8 != 7 4
3 6 == 3 1
5 != 2 1
1 100 6 == 7 2
Ups, 22 iterations in total! Anyone can decide which approach is more "elegant"
source to share