LeetCode 494. 目标和

Categories:

Tags:

题目描述
思路分析
参考代码

题目描述

🔥 494. 目标和

思路分析

题目可以转换为：子集求和问题

01 背包组合问题 x + y = sum(nums) x - y = S 2 * x = sum(nums) + S

参考代码

write your code here

🍏 点击查看 Java 题解

class Solution {
    public int findTargetSumWays(int[] nums, int S) {
        int sum = S;
        for (int num : nums) {
            sum += num;
        }
        if (sum < 0 || sum % 2 != 0) {
            return 0;
        }
        int target = sum / 2;
        int[] dp = new int[target + 1]; // dp[i] 表示能够组成和为 i 的方式数
        dp[0] = 1;
        for (int num : nums) {
            for (int j = target; j >= num; j--) {
                dp[j] += dp[j - num];
            }
        }
        return dp[target];
    }
}

class Solution {
    public int findTargetSumWays(int[] nums, int S) {
        int sum = S;
        for (int num : nums) {
            sum += num;
        }
        if (sum < 0 || sum % 2 != 0) {
            return 0;
        }
        int target = sum / 2;

        Arrays.sort(nums);
        List<List<Integer>> res = new ArrayList<>();
        backtrack(nums, target, new ArrayList<>(), res, 0);
        return res.size();
    }

    public void backtrack(int[] nums, int pathSum, List<Integer> path, List<List<Integer>> res, int start) {
        if (pathSum == 0) {
            res.add(new ArrayList<>(path)); // 找到一个组合，加入结果集
        } else if (pathSum < 0) { // 剪枝，如果 pathSum 小于 0，说明当前组合不合法，直接返回
            return;
        }
        for (int i = start; i < nums.length; i++) {
            path.add(nums[i]);
            backtrack(nums, pathSum - nums[i], path, res, i + 1);
            path.remove(path.size() - 1);
        }
    }
}

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2022/25056900