How to check if any subset of a given set of numbers can sum up to a given number
$begingroup$
Given a number, say $x$, and a set of numbers made up of only $k$ different numbers, where each of the $k$ numbers is repeated $n_1,n_2,dots n_k$ times. How do I tell if it is possible to find a subset such that it sums to $x$.
E.g.: $$x=6 , k=3$$ $$S={1,2,3,3,2,1}$$ $$n_1=2, n_2=2, n_3=2$$ $$1+2+3=6$$ so its possible.
All the numbers in the set are square free.
combinatorics number-theory algorithms
$endgroup$
|
show 1 more comment
$begingroup$
Given a number, say $x$, and a set of numbers made up of only $k$ different numbers, where each of the $k$ numbers is repeated $n_1,n_2,dots n_k$ times. How do I tell if it is possible to find a subset such that it sums to $x$.
E.g.: $$x=6 , k=3$$ $$S={1,2,3,3,2,1}$$ $$n_1=2, n_2=2, n_3=2$$ $$1+2+3=6$$ so its possible.
All the numbers in the set are square free.
combinatorics number-theory algorithms
$endgroup$
1
$begingroup$
This is known as the subset sum problem and as far as is known the best algorithms have exponential complexity. Are you interested in a description of searching for a solution by backtracking?
$endgroup$
– hardmath
Oct 11 '15 at 16:22
$begingroup$
what if k<=10, is there a better way to do this ? I already know about the subset sum problem, but its not fast enough
$endgroup$
– Hemanth immanuel
Oct 11 '15 at 16:33
$begingroup$
Yes, all the numbers and 'x' are positive, there is one other thing that i forgot to mention, all the numbers in the set are square-free
$endgroup$
– Hemanth immanuel
Oct 11 '15 at 16:34
$begingroup$
It seems odd that you would edit the Question to say the numbers are square-free, but omit that they are nonnegative integers (if I understood correctly). Certainly the only possible sums $x$ will be multiples of the GCD of all your potential summands, so without loss of generality they have combined GCD one. Knowing the underlying set of $k$ values is small helps, but I don't see that being square-free is relevant.
$endgroup$
– hardmath
Oct 11 '15 at 16:51
$begingroup$
've found out how to do it a bit faster, I'm posting it here just in case you want to know how @hardmath: For each of the 'k' different numbers, we will create new summands containing the number 1,2,4,... times until its no longer possible to create new summands, so any number having l*ni as a summand for some 'l' and ni can also be expressed as a sum of these new summands, but now, there will be at most logN summands for each distinct number
$endgroup$
– Hemanth immanuel
Oct 16 '15 at 14:04
|
show 1 more comment
$begingroup$
Given a number, say $x$, and a set of numbers made up of only $k$ different numbers, where each of the $k$ numbers is repeated $n_1,n_2,dots n_k$ times. How do I tell if it is possible to find a subset such that it sums to $x$.
E.g.: $$x=6 , k=3$$ $$S={1,2,3,3,2,1}$$ $$n_1=2, n_2=2, n_3=2$$ $$1+2+3=6$$ so its possible.
All the numbers in the set are square free.
combinatorics number-theory algorithms
$endgroup$
Given a number, say $x$, and a set of numbers made up of only $k$ different numbers, where each of the $k$ numbers is repeated $n_1,n_2,dots n_k$ times. How do I tell if it is possible to find a subset such that it sums to $x$.
E.g.: $$x=6 , k=3$$ $$S={1,2,3,3,2,1}$$ $$n_1=2, n_2=2, n_3=2$$ $$1+2+3=6$$ so its possible.
All the numbers in the set are square free.
combinatorics number-theory algorithms
combinatorics number-theory algorithms
edited Oct 11 '15 at 16:47
Hemanth immanuel
asked Oct 11 '15 at 16:10
Hemanth immanuelHemanth immanuel
112
112
1
$begingroup$
This is known as the subset sum problem and as far as is known the best algorithms have exponential complexity. Are you interested in a description of searching for a solution by backtracking?
$endgroup$
– hardmath
Oct 11 '15 at 16:22
$begingroup$
what if k<=10, is there a better way to do this ? I already know about the subset sum problem, but its not fast enough
$endgroup$
– Hemanth immanuel
Oct 11 '15 at 16:33
$begingroup$
Yes, all the numbers and 'x' are positive, there is one other thing that i forgot to mention, all the numbers in the set are square-free
$endgroup$
– Hemanth immanuel
Oct 11 '15 at 16:34
$begingroup$
It seems odd that you would edit the Question to say the numbers are square-free, but omit that they are nonnegative integers (if I understood correctly). Certainly the only possible sums $x$ will be multiples of the GCD of all your potential summands, so without loss of generality they have combined GCD one. Knowing the underlying set of $k$ values is small helps, but I don't see that being square-free is relevant.
$endgroup$
– hardmath
Oct 11 '15 at 16:51
$begingroup$
've found out how to do it a bit faster, I'm posting it here just in case you want to know how @hardmath: For each of the 'k' different numbers, we will create new summands containing the number 1,2,4,... times until its no longer possible to create new summands, so any number having l*ni as a summand for some 'l' and ni can also be expressed as a sum of these new summands, but now, there will be at most logN summands for each distinct number
$endgroup$
– Hemanth immanuel
Oct 16 '15 at 14:04
|
show 1 more comment
1
$begingroup$
This is known as the subset sum problem and as far as is known the best algorithms have exponential complexity. Are you interested in a description of searching for a solution by backtracking?
$endgroup$
– hardmath
Oct 11 '15 at 16:22
$begingroup$
what if k<=10, is there a better way to do this ? I already know about the subset sum problem, but its not fast enough
$endgroup$
– Hemanth immanuel
Oct 11 '15 at 16:33
$begingroup$
Yes, all the numbers and 'x' are positive, there is one other thing that i forgot to mention, all the numbers in the set are square-free
$endgroup$
– Hemanth immanuel
Oct 11 '15 at 16:34
$begingroup$
It seems odd that you would edit the Question to say the numbers are square-free, but omit that they are nonnegative integers (if I understood correctly). Certainly the only possible sums $x$ will be multiples of the GCD of all your potential summands, so without loss of generality they have combined GCD one. Knowing the underlying set of $k$ values is small helps, but I don't see that being square-free is relevant.
$endgroup$
– hardmath
Oct 11 '15 at 16:51
$begingroup$
've found out how to do it a bit faster, I'm posting it here just in case you want to know how @hardmath: For each of the 'k' different numbers, we will create new summands containing the number 1,2,4,... times until its no longer possible to create new summands, so any number having l*ni as a summand for some 'l' and ni can also be expressed as a sum of these new summands, but now, there will be at most logN summands for each distinct number
$endgroup$
– Hemanth immanuel
Oct 16 '15 at 14:04
1
1
$begingroup$
This is known as the subset sum problem and as far as is known the best algorithms have exponential complexity. Are you interested in a description of searching for a solution by backtracking?
$endgroup$
– hardmath
Oct 11 '15 at 16:22
$begingroup$
This is known as the subset sum problem and as far as is known the best algorithms have exponential complexity. Are you interested in a description of searching for a solution by backtracking?
$endgroup$
– hardmath
Oct 11 '15 at 16:22
$begingroup$
what if k<=10, is there a better way to do this ? I already know about the subset sum problem, but its not fast enough
$endgroup$
– Hemanth immanuel
Oct 11 '15 at 16:33
$begingroup$
what if k<=10, is there a better way to do this ? I already know about the subset sum problem, but its not fast enough
$endgroup$
– Hemanth immanuel
Oct 11 '15 at 16:33
$begingroup$
Yes, all the numbers and 'x' are positive, there is one other thing that i forgot to mention, all the numbers in the set are square-free
$endgroup$
– Hemanth immanuel
Oct 11 '15 at 16:34
$begingroup$
Yes, all the numbers and 'x' are positive, there is one other thing that i forgot to mention, all the numbers in the set are square-free
$endgroup$
– Hemanth immanuel
Oct 11 '15 at 16:34
$begingroup$
It seems odd that you would edit the Question to say the numbers are square-free, but omit that they are nonnegative integers (if I understood correctly). Certainly the only possible sums $x$ will be multiples of the GCD of all your potential summands, so without loss of generality they have combined GCD one. Knowing the underlying set of $k$ values is small helps, but I don't see that being square-free is relevant.
$endgroup$
– hardmath
Oct 11 '15 at 16:51
$begingroup$
It seems odd that you would edit the Question to say the numbers are square-free, but omit that they are nonnegative integers (if I understood correctly). Certainly the only possible sums $x$ will be multiples of the GCD of all your potential summands, so without loss of generality they have combined GCD one. Knowing the underlying set of $k$ values is small helps, but I don't see that being square-free is relevant.
$endgroup$
– hardmath
Oct 11 '15 at 16:51
$begingroup$
've found out how to do it a bit faster, I'm posting it here just in case you want to know how @hardmath: For each of the 'k' different numbers, we will create new summands containing the number 1,2,4,... times until its no longer possible to create new summands, so any number having l*ni as a summand for some 'l' and ni can also be expressed as a sum of these new summands, but now, there will be at most logN summands for each distinct number
$endgroup$
– Hemanth immanuel
Oct 16 '15 at 14:04
$begingroup$
've found out how to do it a bit faster, I'm posting it here just in case you want to know how @hardmath: For each of the 'k' different numbers, we will create new summands containing the number 1,2,4,... times until its no longer possible to create new summands, so any number having l*ni as a summand for some 'l' and ni can also be expressed as a sum of these new summands, but now, there will be at most logN summands for each distinct number
$endgroup$
– Hemanth immanuel
Oct 16 '15 at 14:04
|
show 1 more comment
1 Answer
1
active
oldest
votes
$begingroup$
There are several studied variations on the Subset Sum Problem. The one described here, at least for arbitrary multisets of natural numbers, is essentially the Bounded Knapsack Decision Problem, where "bounded" refers to the number of items of the ith kind having a bound $n_i$.
These decision problems are known to be NP-complete, and unless P=NP, there will be no algorithm that (over general inputs) has better than exponential complexity (exponential in the size of input data, measured by counting bits). However there is a pseudo-polynomial time algorithm based on dynamic programming, and the distinction is discussed under Knapsack problem — NP-complete despite dynamic programming solution?.
It is therefore "believed to be one of the easier $mathcal{NP}$-hard problems" (Where are the hard knapsack problems?, Pisinger (2003)).
If the algorithms for exactly solving this problem are not satisfactory in performance, then as a fallback one might consider approximate algorithms or probabilistic algorithms. By the first of these alternatives we mean answering a "relaxed" question about whether we can come within a tolerance of the required sum $x$, and there exist polynomial time algorithms (but whose complexity nonetheless depends on the allowed tolerance). See Bounded Knapsack Problem for a detailed analysis (Chapter 3 of the book Knapsack Problems - Algorithms and Computer Implementations by Martello and Toth, 1990).
By probabilistic algorithm we mean a randomized search that has a significant likelihood of finding (within polynomial bounded time) the exact sum $x$ if it is feasible, but may fail to do so (within the time bound) even if a solution exists. For example, simulated annealing is often proposed as a search technique. A recent proposal (Gao, Qui and Cao, 2014) is Estimation of Distribution Algorithms for Knapsack Problem, which has good references to the literature.
$endgroup$
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f1474943%2fhow-to-check-if-any-subset-of-a-given-set-of-numbers-can-sum-up-to-a-given-numbe%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
There are several studied variations on the Subset Sum Problem. The one described here, at least for arbitrary multisets of natural numbers, is essentially the Bounded Knapsack Decision Problem, where "bounded" refers to the number of items of the ith kind having a bound $n_i$.
These decision problems are known to be NP-complete, and unless P=NP, there will be no algorithm that (over general inputs) has better than exponential complexity (exponential in the size of input data, measured by counting bits). However there is a pseudo-polynomial time algorithm based on dynamic programming, and the distinction is discussed under Knapsack problem — NP-complete despite dynamic programming solution?.
It is therefore "believed to be one of the easier $mathcal{NP}$-hard problems" (Where are the hard knapsack problems?, Pisinger (2003)).
If the algorithms for exactly solving this problem are not satisfactory in performance, then as a fallback one might consider approximate algorithms or probabilistic algorithms. By the first of these alternatives we mean answering a "relaxed" question about whether we can come within a tolerance of the required sum $x$, and there exist polynomial time algorithms (but whose complexity nonetheless depends on the allowed tolerance). See Bounded Knapsack Problem for a detailed analysis (Chapter 3 of the book Knapsack Problems - Algorithms and Computer Implementations by Martello and Toth, 1990).
By probabilistic algorithm we mean a randomized search that has a significant likelihood of finding (within polynomial bounded time) the exact sum $x$ if it is feasible, but may fail to do so (within the time bound) even if a solution exists. For example, simulated annealing is often proposed as a search technique. A recent proposal (Gao, Qui and Cao, 2014) is Estimation of Distribution Algorithms for Knapsack Problem, which has good references to the literature.
$endgroup$
add a comment |
$begingroup$
There are several studied variations on the Subset Sum Problem. The one described here, at least for arbitrary multisets of natural numbers, is essentially the Bounded Knapsack Decision Problem, where "bounded" refers to the number of items of the ith kind having a bound $n_i$.
These decision problems are known to be NP-complete, and unless P=NP, there will be no algorithm that (over general inputs) has better than exponential complexity (exponential in the size of input data, measured by counting bits). However there is a pseudo-polynomial time algorithm based on dynamic programming, and the distinction is discussed under Knapsack problem — NP-complete despite dynamic programming solution?.
It is therefore "believed to be one of the easier $mathcal{NP}$-hard problems" (Where are the hard knapsack problems?, Pisinger (2003)).
If the algorithms for exactly solving this problem are not satisfactory in performance, then as a fallback one might consider approximate algorithms or probabilistic algorithms. By the first of these alternatives we mean answering a "relaxed" question about whether we can come within a tolerance of the required sum $x$, and there exist polynomial time algorithms (but whose complexity nonetheless depends on the allowed tolerance). See Bounded Knapsack Problem for a detailed analysis (Chapter 3 of the book Knapsack Problems - Algorithms and Computer Implementations by Martello and Toth, 1990).
By probabilistic algorithm we mean a randomized search that has a significant likelihood of finding (within polynomial bounded time) the exact sum $x$ if it is feasible, but may fail to do so (within the time bound) even if a solution exists. For example, simulated annealing is often proposed as a search technique. A recent proposal (Gao, Qui and Cao, 2014) is Estimation of Distribution Algorithms for Knapsack Problem, which has good references to the literature.
$endgroup$
add a comment |
$begingroup$
There are several studied variations on the Subset Sum Problem. The one described here, at least for arbitrary multisets of natural numbers, is essentially the Bounded Knapsack Decision Problem, where "bounded" refers to the number of items of the ith kind having a bound $n_i$.
These decision problems are known to be NP-complete, and unless P=NP, there will be no algorithm that (over general inputs) has better than exponential complexity (exponential in the size of input data, measured by counting bits). However there is a pseudo-polynomial time algorithm based on dynamic programming, and the distinction is discussed under Knapsack problem — NP-complete despite dynamic programming solution?.
It is therefore "believed to be one of the easier $mathcal{NP}$-hard problems" (Where are the hard knapsack problems?, Pisinger (2003)).
If the algorithms for exactly solving this problem are not satisfactory in performance, then as a fallback one might consider approximate algorithms or probabilistic algorithms. By the first of these alternatives we mean answering a "relaxed" question about whether we can come within a tolerance of the required sum $x$, and there exist polynomial time algorithms (but whose complexity nonetheless depends on the allowed tolerance). See Bounded Knapsack Problem for a detailed analysis (Chapter 3 of the book Knapsack Problems - Algorithms and Computer Implementations by Martello and Toth, 1990).
By probabilistic algorithm we mean a randomized search that has a significant likelihood of finding (within polynomial bounded time) the exact sum $x$ if it is feasible, but may fail to do so (within the time bound) even if a solution exists. For example, simulated annealing is often proposed as a search technique. A recent proposal (Gao, Qui and Cao, 2014) is Estimation of Distribution Algorithms for Knapsack Problem, which has good references to the literature.
$endgroup$
There are several studied variations on the Subset Sum Problem. The one described here, at least for arbitrary multisets of natural numbers, is essentially the Bounded Knapsack Decision Problem, where "bounded" refers to the number of items of the ith kind having a bound $n_i$.
These decision problems are known to be NP-complete, and unless P=NP, there will be no algorithm that (over general inputs) has better than exponential complexity (exponential in the size of input data, measured by counting bits). However there is a pseudo-polynomial time algorithm based on dynamic programming, and the distinction is discussed under Knapsack problem — NP-complete despite dynamic programming solution?.
It is therefore "believed to be one of the easier $mathcal{NP}$-hard problems" (Where are the hard knapsack problems?, Pisinger (2003)).
If the algorithms for exactly solving this problem are not satisfactory in performance, then as a fallback one might consider approximate algorithms or probabilistic algorithms. By the first of these alternatives we mean answering a "relaxed" question about whether we can come within a tolerance of the required sum $x$, and there exist polynomial time algorithms (but whose complexity nonetheless depends on the allowed tolerance). See Bounded Knapsack Problem for a detailed analysis (Chapter 3 of the book Knapsack Problems - Algorithms and Computer Implementations by Martello and Toth, 1990).
By probabilistic algorithm we mean a randomized search that has a significant likelihood of finding (within polynomial bounded time) the exact sum $x$ if it is feasible, but may fail to do so (within the time bound) even if a solution exists. For example, simulated annealing is often proposed as a search technique. A recent proposal (Gao, Qui and Cao, 2014) is Estimation of Distribution Algorithms for Knapsack Problem, which has good references to the literature.
edited Apr 13 '17 at 12:48
Community♦
1
1
answered Oct 17 '15 at 21:10
hardmathhardmath
29.1k953101
29.1k953101
add a comment |
add a comment |
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f1474943%2fhow-to-check-if-any-subset-of-a-given-set-of-numbers-can-sum-up-to-a-given-numbe%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
1
$begingroup$
This is known as the subset sum problem and as far as is known the best algorithms have exponential complexity. Are you interested in a description of searching for a solution by backtracking?
$endgroup$
– hardmath
Oct 11 '15 at 16:22
$begingroup$
what if k<=10, is there a better way to do this ? I already know about the subset sum problem, but its not fast enough
$endgroup$
– Hemanth immanuel
Oct 11 '15 at 16:33
$begingroup$
Yes, all the numbers and 'x' are positive, there is one other thing that i forgot to mention, all the numbers in the set are square-free
$endgroup$
– Hemanth immanuel
Oct 11 '15 at 16:34
$begingroup$
It seems odd that you would edit the Question to say the numbers are square-free, but omit that they are nonnegative integers (if I understood correctly). Certainly the only possible sums $x$ will be multiples of the GCD of all your potential summands, so without loss of generality they have combined GCD one. Knowing the underlying set of $k$ values is small helps, but I don't see that being square-free is relevant.
$endgroup$
– hardmath
Oct 11 '15 at 16:51
$begingroup$
've found out how to do it a bit faster, I'm posting it here just in case you want to know how @hardmath: For each of the 'k' different numbers, we will create new summands containing the number 1,2,4,... times until its no longer possible to create new summands, so any number having l*ni as a summand for some 'l' and ni can also be expressed as a sum of these new summands, but now, there will be at most logN summands for each distinct number
$endgroup$
– Hemanth immanuel
Oct 16 '15 at 14:04