integers. The integers are described by their binary representation. Each input integer can be represented by 3nL bits, divided into 3n zones of L bits. Each zone corresponds to a vertex. For each edge (w,x,y) in the 3DM instance, there is an integer in the SSP instance, in which exactly three bits are "1": the least-significant bits in the zones of the vertices w, x, and y. For example, if n=10 and L=3, and W=(0,...,9), X=(10,...,19), Y=(20,...,29), then the edge (0, 10, 20) is represented by the number (20+230+260). The target sum T in the SSP instance is set to an integer with "1" in the least-significant bit of every zone, that is, (20+21+...+23n-1). If the 3DM instance has a perfect matching, then summing the corresponding integers in the SSP instance yields exactly T. Conversely, if the SSP instance has a subset with sum exactly T, then, since the zones are sufficiently large so that there are no "carries" from one zone to the next, the sum must correspond to a perfect matching in the 3DM instance. The following variants are also known to be NP-hard: The input integers can be both positive and negative, and the target-sum T = 0. This can be proved by reduction from the variant with positive integers. Denote that variant by SubsetSumPositive and the current variant by SubsetSumZero. Given an instance (S, T) of SubsetSumPositive, construct an instance of SubsetSumZero by adding a single element with value −T. Given a solution to the SubsetSumPositive instance, adding the −T yields a solution to the SubsetSumZero instance. Conversely, given a solution to the SubsetSumZero instance, it must contain the −T (since all integers in S are positive), so to get a sum of zero, it must also contain a subset of S with a sum of +T, which is a solution of the SubsetSumPositive instance. The input integers are positive, and T = sum(S)/2. This can also be proved by reduction from the general variant; see partition problem. Exponential time algorithms There are several ways to solve SSP in time exponential in n. Inclusion–exclusion The most naïve algorithm would be to cycle through all subsets of n numbers and, for every one of them, check if the subset sums to the right number. The running time is of order , since there are subsets and, to check each subset, we need to sum at most n