目标和

/*
题目思路：
可以用Java Stream来实现。我们将数组元素转换成其正负两种形式的数组，然后通过flatMap操作来合并两种可能性。
然后，使用collect(Collectors.toList())收集所有可能的组合。最后，通过stream().filter()来筛选出所有满足条件的组合。
*/
 
import java.util.Arrays;
import java.util.List;
import java.util.stream.Collectors;
 
public class Solution {
    public int findTargetSumWays(int[] nums, int target) {
        List<Integer> sums = Arrays.stream(nums)
                .boxed()
                .flatMap(num -> Arrays.asList(num, -num).stream())
                .collect(Collectors.toList());
 
        return (int) findCombinations(sums, 0, 0, target);
    }
 
    private long findCombinations(List<Integer> nums, int index, int currentSum, int target) {
        if (index == nums.size() / 2) {
            return currentSum == target ? 1 : 0;
        }
        return findCombinations(nums, index + 1, currentSum + nums.get(index * 2), target)
                + findCombinations(nums, index + 1, currentSum + nums.get(index * 2 + 1), target);
    }
}