# Strict partitions of a positive integer

OEIS A000009 counts the number of strict partitions of the integers. A strict partition of a nonnegative integer `n` is a set of positive integers (so no repetition is allowed, and order does not matter) that sum to `n`.

For example, 5 has three strict partitions: `5`, `4,1`, and `3,2`.

10 has ten partitions:

``````10
9,1
8,2
7,3
6,4
7,2,1
6,3,1
5,4,1
5,3,2
4,3,2,1
``````

## Challenge

Given a nonnegative integer `n`<1000, output the number of strict partitions it has.

### Test cases:

``````0 -> 1

42 -> 1426
``````

Here is a list of the strict partition numbers from 0 to 55, from OEIS:

``````[1,1,1,2,2,3,4,5,6,8,10,12,15,18,22,27,32,38,46,54,64,76,89,104,122,142,165,192,222,256,296,340,390,448,512,585,668,760,864,982,1113,1260,1426,1610,1816,2048,2304,2590,2910,3264,3658,4097,4582,5120,5718,6378]
``````

This is , so the shortest solution in bytes wins.

-

# Mathematica, 11 bytes

``````PartitionsQ
``````

Test case

``````PartitionsQ@Range[10]
(* {1,1,2,2,3,4,5,6,8,10} *)
``````
-

``````f n=sum[1|x<-mapM(:[0])[1..n],sum x==n]
``````

The function `(:[0])` converts a number `k` to the list `[k,0]`. So,

``````mapM(:[0])[1..n]
``````

computes the Cartesian product of `[1,0],[2,0],...,[n,0]`, which gives all subsets of `[1..n]` with 0's standing for omitted elements. The strict partitions of `n` correspond to such lists with sum `n`. Such elements are counted by a list comprehension, which is shorter than `length.filter`.

-
Brilliant! I was looking for a replacement for `subsequences` (+ `import`) in my answer myself, but didn't succeed so far. – nimi Feb 13 at 2:52

## ES6, 64 bytes

``````f=(n,k=0)=>[...Array(n)].reduce((t,_,i)=>n-i>i&i>k?t+f(n-i,i):t,1)
``````

Works by recursive trial subtraction. `k` is the number that was last subtracted, and the next number to be subtracted must be larger (but not so large that an even larger number cannot be subtracted). 1 is added because you can always subtract `n` itself. (Also since this is recursive I have to take care that all of my variables are local.)

-

# Pyth, 7 bytes

``````l{I#./Q
``````
• Take the input (`Q`).
• Find its partitions (`./`).
• Filter it (`#`) on uniquify (`{`) not changing (`I`) the partition. This removes partitions with duplicates.
• Find the result's length (`l`).
-

## Python 2, 49 bytes

``````f=lambda n,k=1:n/k and f(n-k,k+1)+f(n,k+1)or n==0
``````

The recursion branches at every potential summand `k` from `1` to `n` to decide whether it should be included. Each included summand is subtracted from the desired sum `n`, and at the end, if `n=0` remains, that path is counted.

-

``````0%0=1
_%0=0
n%k=n%(k-1)+(n-k)%(k-1)
f n=n%n
``````

The binary function `n%k` counts the number of strict partitions of `n` into parts with a maximum part `k`, so the desired function is `f n=n%n`. Each value `k` can be included, which decreases `n` by `k`, or excluded, and either way the new maximum `k` is one lower, giving the recursion `n%k=n%(k-1)+(n-k)%(k-1)`.

-

# Python, 68 bytes

``````p=lambda n,d=0:sum(p(n-k,n-2*k+1)for k in range(1,n-d+1))if n else 1
``````

Just call the anonymous function passing the nonnegative integer `n` as argument... and wait the end of the universe.

-
make it `n>0`, you save a byte and go faster (i believe you recurse on negative numbers) :P – st0le Feb 12 at 23:58
Also, Memoizing this kind of speeds it up – st0le Feb 13 at 0:00
Cant you change your if statement to: `return sum(...)if n else 1` – andlrc Feb 13 at 0:07
@dev-null Sure, thanks! – Bob Feb 13 at 10:03
@randomra Of course, of course... – Bob Feb 15 at 17:28

# Julia, 53 bytes

``````n->endof(collect(filter(p->p==∪(p),partitions(n))))
``````

This is an anonymous function that accepts an integer and returns an integer. To call it, assign it to a variable.

We get the integer partitions using `partitions`, `filter` to only those with distinct summands, `collect` into an array, and find the last index (i.e. the length) using `endof`.

-

``````import Data.List
Usage example: `map h [0..10]` -> `[1,1,1,2,2,3,4,5,6,8,10]`.
It's a simple brute-force approach. Check the sums of all subsequences of `1..x`. This works for `x == 0`, too, because all subsequences of `[1..0]` are `[[]]` and the sum of `[]` is `0`.