2
$\begingroup$

I was told to do this using recursion (no loops and cannot be in constant n time). We essentially have a linked list starting at 1 going until n. I have figured out how to do this mathematically, but not recursively quite yet. The method being written takes an int as a parameter. Thanks for the help.

$\endgroup$

migrated from cs.stackexchange.com Dec 9 '14 at 13:24

This question came from our site for students, researchers and practitioners of computer science.

1
$\begingroup$

Let $n\geq1$. There are $2^{n-1}$ subsets $A\subset\{2,3,\ldots, n\}$, and for each such $A$ exactly one of $A$ and $A\cup\{1\}$ has even weight. Since all subsets $\bar A\subset[n]$ are produced in this way exactly once the number of $\bar A\in[n]$ with even weight is $2^{n-1}$.

$\endgroup$
  • $\begingroup$ Stated differently, given a subset $A \subseteq \{2,\ldots,n\}$, exactly one of $A,A\cup\{1\}$ has even weight. $\endgroup$ – Yuval Filmus Dec 9 '14 at 17:20
0
$\begingroup$

Neither looping nor recursion is required. The sum of a set of integers is even if, and only if, the set contains an even number of odd numbers.

If recursion is required, you can use the standard idea that a subset of $\{1, \dots, n\}$ either contains $n$ or it doesn't. So the desired total is the number of even-sum subsets of $\{1, \dots, n-1\}$ plus the number of subsets $S$ of $\{1, \dots, n-1\}$ such that $S\cup\{n\}$ has even sum.

$\endgroup$
  • $\begingroup$ I am aware that this is the answer, but for some reason, they want to see recursion. So I guess i'll just multiply 2 over and over again... $\endgroup$ – csfool Dec 9 '14 at 13:15
  • $\begingroup$ Well this gives you a recursive way of computing the number of even (and odd) subsets $\endgroup$ – Myself Dec 9 '14 at 13:27
0
$\begingroup$

Let $S_n=\{1, 2, \ldots, n\}$. To make life simple, let us call the subsets with sum of elements even as even subsets and similarly, the subsets with sum of elements odd as odd subsets.

Assume $e(n)$ and $o(n)$ as the number of even subsets and odd subsets respectively.

Then, if $n+1$ is odd, every even subset of $S_{n+1}$ is EITHER even subset of $S_{n}$ OR odd subset of $S_{n}$ unioned with $\{n+1\}$. That is, if $n+1$ is odd, then $e(n+1) = e(n)+o(n)$.

Similarly, if $n+1$ is even, every even subset of $S_{n+1}$ is EITHER even subset of $S_{n}$ OR even subset of $S_{n}$ unioned with $\{n+1\}$. That is, if $n+1$ is even, then $e(n+1) = 2e(n)$.

So, we have a recursion:

$$ e(n+1) = \left\{\begin{array}{ll} e(n)+o(n) & \mbox{ odd } n+1\\ 2e(n) & \mbox{ even } n+1\end{array}\right. $$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy