问对给定目标的5的倍数之和

EN

package so5987154;

import java.util.Collection;
import java.util.List;
import java.util.Set;

import com.google.common.collect.Lists;
import com.google.common.collect.Sets;

public class Summation {
    /**
     * Sum of start and every element of the collection.
     * 
     * @param start
     *            starting value for the sum
     * @param list
     *            Collection to sum.
     * @return the sum.
     */
    private int sum(final Integer start, final Collection<Integer> list) {
        int sum = start;

        for (final int i : list) {
            sum += i;
        }

        return sum;
    }

    /**
     * Given an array of ints, is it possible to choose a group of some of the ints, such that the group sums to the given target
     * with these additional constraints: all multiples of 5 in the array must be included in the group. If the value immediately
     * following a multiple of 5 is 1, it must not be chosen.
     * 
     * @param start
     *            not used
     * @param nums
     *            array of int (input)
     * @param target
     *            target value for the summation
     * @return true if we found a group that meet the criteria.
     */
    public boolean groupSum5(final int start, final int[] nums, final int target) {
        // list of values that need to be included (multiple of 5)
        final List<Integer> fixed = Lists.newArrayList();

        // list of value that can be included (anything but 1 preceded by a multiple of 5)
        final List<Integer> candidates = Lists.newArrayList();

        // fills candidates and fixed
        for (int i = 0; i < nums.length; i++) {
            final int cand = nums[i];

            if (cand == 1 && i > 0) {
                final int prev = nums[i - 1];
                if (prev % 5 != 0) {
                    candidates.add(cand);
                }
            } else if (cand % 5 == 0) {
                fixed.add(cand);
            } else if (cand <= target) {
                candidates.add(cand);
            }
        }

        // compute the sum of fixed
        final int sumFixed = sum(0, fixed);

        // if the sum of fixed is equals to target we don't need to do anything because
        // we already know we need to return true.
        if (sumFixed == target) {
            return true; // NOPMD
        }

        // if the sum of fixed is greater than target we don't need to do anything because
        // we already know we need to return false (all multiple of 5 must be included)
        // If candidates is empty there's no way we can achieve the desired goal.
        if (sumFixed <= target && !candidates.isEmpty()) {
            // generates all subsets of candidates:
            // { 1, 2 } => {}, {1}, {2}, {1, 2}
            final Set<Set<Integer>> powerSet = Sets.powerSet(Sets.newHashSet(candidates));

            // for each found subset, computes the sum of the subset and add it to the sum of
            // multiples of 5 then compare it to target. If equals => return true.
            for (final Set<Integer> set : powerSet) {
                if (sumFixed + sum(0, set) == target) {
                    return true; // NOPMD
                }
            }
        }

        return false;
    }
}

package so5987154.tests;

import static org.junit.Assert.assertFalse;
import static org.junit.Assert.assertTrue;

import org.junit.Test;

import so5987154.Summation;

@SuppressWarnings("PMD")
public class SummationTest {
    private final Summation s = new Summation();

    @Test
    public void testGroupSum5() {
        assertTrue(s.groupSum5(0, new int[] { 2, 5, 10, 4 }, 19));
        assertTrue(s.groupSum5(0, new int[] { 2, 5, 10, 4 }, 17));
        assertFalse(s.groupSum5(0, new int[] { 2, 5, 10, 4 }, 12));
        assertTrue(s.groupSum5(0, new int[] { 2, 5, 10, 4 }, 19));
        assertTrue(s.groupSum5(0, new int[] { 3, 5, 1 }, 5));
        assertFalse(s.groupSum5(0, new int[] { 3, 5, 1 }, 4));
        assertTrue(s.groupSum5(0, new int[] { 3, 1 }, 4));
        assertFalse(s.groupSum5(0, new int[] { 3, 1 }, 2));
        assertTrue(s.groupSum5(0, new int[] { 1 }, 1));
    }
}