Is it feasible to solve the subset sum problem if all the elements are odd and we also know that whether odd or even no. of elements are used to form the sum for example - If i have the set -{ 9, 13 , 17,7 ,3 ,5, 11 ,15}
The sum is S=65. It is also known that odd no. of elements out of the set are to be used.So, can i know exactly which elements will sum to 65 in polynomial time. Thanks.
I think it is still NP-Hard.
We will reduce the general subset-sum problem to your case when the input numbers are all odd.
Given $y_1, \dots y_n$ and a target sum $K \ge 0$, let $P$ be the sum of the positive numbers and $N$ the sum of negative numbers.
Let $M = 2P + 2|N| + 2K + 1$.
Now set $x_i = 2y_i + M$. Note that: $x_i$ is odd.
Construct set
$$ S = \{x_1, x_2, \dots, x_n\}$$
Run your algorithm (for odd number case) on $S$, $n$, times, with the target sums $$2K + jM, 1 \le j \le n$$
We can show that the original set has a subset of sum $K$, iff at least one of the $n$ sub-problems we just constructed returns a yes answer.
This construction is quite similar to the one here: https://cs.stackexchange.com/questions/10981/subset-sum-reduce-special-to-general-case/10987#10987