labuladong 的算法小抄 > 第二章、手把手刷动态规划 > 背包类型问题 > 动态规划和回溯算法到底谁是谁爹？

动态规划和回溯算法到底谁是谁爹？

读完本文，你不仅学会了算法套路，还可以顺便解决如下题目：

LeetCode	力扣	难度
494. Target Sum	494. 目标和	🟠
-	剑指 Offer II 102. 加减的目标值	🟠

———–

我们前文经常说回溯算法和递归算法有点类似，有的问题如果实在想不出状态转移方程，尝试用回溯算法暴力解决也是一个聪明的策略，总比写不出来解法强。

那么，回溯算法和动态规划到底是啥关系？它俩都涉及递归，算法模板看起来还挺像的，都涉及做「选择」，真的酷似父与子。

那么，它俩具体有啥区别呢？回溯算法和动态规划之间，是否可能互相转化呢？

今天就用力扣第 494 题「目标和」来详细对比一下回溯算法和动态规划，题目如下：

给你输入一个非负整数数组 nums 和一个目标值 target，现在你可以给每一个元素 nums[i] 添加正号 + 或负号 -，请你计算有几种符号的组合能够使得 nums 中元素的和为 target。

函数的签名如下：

int findTargetSumWays(int[] nums, int target);

// 注意：cpp 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

int findTargetSumWays(vector<int>& nums, int target);

# 注意：python 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
# 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

def findTargetSumWays(nums: List[int], target: int) -> int:

// 注意：go 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

func findTargetSumWays(nums []int, target int) int {

// 注意：javascript 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

var findTargetSumWays = function(nums, target) {};

比如说输入 nums = [1,3,1,4,2], target = 5，算法返回 3，因为有如下 3 种组合能够使得 target 等于 5：

-1+3+1+4-2=5
-1+3+1+4-2=5
+1-3+1+4+2=5

nums 的元素也有可能包含 0，我们可以正常地给 0 分配正负号。

一、回溯思路

其实我第一眼看到这个题目，花了两分钟就写出了一个回溯解法。

任何算法的核心都是穷举，回溯算法就是一个暴力穷举算法，前文回溯算法解题框架就写了回溯算法框架：

def backtrack(路径, 选择列表):
    if 满足结束条件:
        result.add(路径)
        return
    
    for 选择 in 选择列表:
        做选择
        backtrack(路径, 选择列表)
        撤销选择

关键就是搞清楚什么是「选择」，而对于这道题，「选择」不是明摆着的吗？对于每个数字 nums[i]，我们可以选择给一个正号 + 或者一个负号 -，然后利用回溯模板穷举出来所有可能的结果，数一数到底有几种组合能够凑出 target 不就行了嘛？

伪码思路如下：

def backtrack(nums, i):
    if i == len(nums):
        if 达到 target:
            result += 1
        return
    
    for op in { +1, -1 }:
        选择 op * nums[i]
        # 穷举 nums[i + 1] 的选择
        backtrack(nums, i + 1)
        撤销选择

如果看过我们之前的几篇回溯算法文章，这个代码可以说是比较简单的了：

class Solution {
    int result = 0;

    /* 主函数 */
    public int findTargetSumWays(int[] nums, int target) {
        if (nums.length == 0) return 0;
        backtrack(nums, 0, target);
        return result;
    }

    /* 回溯算法模板 */
    void backtrack(int[] nums, int i, int remain) {
        // base case
        if (i == nums.length) {
            if (remain == 0) {
                // 说明恰好凑出 target
                result++;
            }
            return;
        }
        // 给 nums[i] 选择 - 号
        remain += nums[i];
        // 穷举 nums[i + 1]
        backtrack(nums, i + 1, remain);
        // 撤销选择
        remain -= nums[i]; 
        
        // 给 nums[i] 选择 + 号
        remain -= nums[i];
        // 穷举 nums[i + 1]
        backtrack(nums, i + 1, remain);
        // 撤销选择
        remain += nums[i];
    }
}

// 注意：cpp 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

class Solution {
    int result = 0;

    /* 主函数 */
public:
    int findTargetSumWays(vector<int>& nums, int target) {
        if (nums.size() == 0) return 0;
        backtrack(nums, 0, target);
        return result;
    }

    /* 回溯算法模板 */
    void backtrack(vector<int>& nums, int i, int remain) {
        // base case
        if (i == nums.size()) {
            if (remain == 0) {
                // 说明恰好凑出 target
                result++;
            }
            return;
        }
        // 给 nums[i] 选择 - 号
        remain += nums[i];
        // 穷举 nums[i + 1]
        backtrack(nums, i + 1, remain);
        // 撤销选择
        remain -= nums[i]; 
        
        // 给 nums[i] 选择 + 号
        remain -= nums[i];
        // 穷举 nums[i + 1]
        backtrack(nums, i + 1, remain);
        // 撤销选择
        remain += nums[i];
    }
};

# 注意：python 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
# 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

class Solution:
    def __init__(self):
        self.result = 0

    # 主函数 
    def findTargetSumWays(self, nums: List[int], target: int) -> int:
        if len(nums) == 0:
            return 0
        self.backtrack(nums, 0, target)
        return self.result

    # 回溯算法模板 
    def backtrack(self, nums: List[int], i: int, remain: int):
        # base case 
        if i == len(nums):
            if remain == 0:
                # 说明恰好凑出 target 
                self.result += 1
            return
        # 给 nums[i] 选择 - 号 
        remain += nums[i]
        # 穷举 nums[i + 1] 
        self.backtrack(nums, i + 1, remain)
        # 撤销选择 
        remain -= nums[i]

        # 给 nums[i] 选择 + 号 
        remain -= nums[i]
        # 穷举 nums[i + 1] 
        self.backtrack(nums, i + 1, remain)
        # 撤销选择 
        remain += nums[i]

// 注意：go 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

func findTargetSumWays(nums []int, target int) int {
    var result int
    backtrack(nums, 0, target, &result)
    return result
}

func backtrack(nums []int, i, remain int, result *int) {
    // base case
    if i == len(nums) {
        if remain == 0 {
            // 说明恰好凑出 target
            (*result)++
        }
        return
    }
    // 给 nums[i] 选择 - 号
    remain += nums[i]
    // 穷举 nums[i + 1]
    backtrack(nums, i+1, remain, result)
    // 撤销选择
    remain -= nums[i]

    // 给 nums[i] 选择 + 号
    remain -= nums[i]
    // 穷举 nums[i + 1]
    backtrack(nums, i+1, remain, result)
    // 撤销选择
    remain += nums[i]
}

// 注意：javascript 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

var findTargetSumWays = function(nums, target) {
  let result = 0;

  /* 回溯算法模板 */
  const backtrack = (nums, i, remain) => {
    // base case
    if (i === nums.length) {
      if (remain === 0) {
        // 说明恰好凑出 target
        result++;
      }
      return;
    }
    // 给 nums[i] 选择 - 号
    remain += nums[i];
    // 穷举 nums[i + 1]
    backtrack(nums, i + 1, remain);
    // 撤销选择
    remain -= nums[i];

    // 给 nums[i] 选择 + 号
    remain -= nums[i];
    // 穷举 nums[i + 1]
    backtrack(nums, i + 1, remain);
    // 撤销选择
    remain += nums[i];
  }

  if (nums.length === 0) return 0;
  backtrack(nums, 0, target);
  return result;
};

有的读者可能问，选择 - 的时候，为什么是 remain += nums[i]，选择 + 的时候，为什么是 remain -= nums[i] 呢，是不是写反了？

不是的，「如何凑出 target」和「如何把 target 减到 0」其实是一样的。我们这里选择后者，因为前者必须给 backtrack 函数多加一个参数，我觉得不美观：

void backtrack(int[] nums, int i, int sum, int target) {
    // base case
    if (i == nums.length) {
        if (sum == target) {
            result++;
        }
        return;
    }
    // ...
}

因此，如果我们给 nums[i] 选择 + 号，就要让 remain - nums[i]，反之亦然。

以上回溯算法可以解决这个问题，时间复杂度为 O(2^N)，N 为 nums 的大小。这个复杂度怎么算的？回忆前文学习数据结构和算法的框架思维，发现这个回溯算法就是个二叉树的遍历问题：

void backtrack(int[] nums, int i, int remain) {
    if (i == nums.length) {
        return;
    }
    backtrack(nums, i + 1, remain - nums[i]);
    backtrack(nums, i + 1, remain + nums[i]);
}

// 注意：cpp 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

void backtrack(vector<int>& nums, int i, int remain) {
    if (i == nums.size()) {
        return;
    }
    backtrack(nums, i + 1, remain - nums[i]);
    backtrack(nums, i + 1, remain + nums[i]);
}

# 注意：python 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
# 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

def backtrack(nums: List[int], i: int, remain: int) -> None:
    if i == len(nums):
        return
    backtrack(nums, i + 1, remain - nums[i])
    backtrack(nums, i + 1, remain + nums[i])

// 注意：go 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

func backtrack(nums []int, i int, remain int) {
    if i == len(nums) {
        return
    }
    backtrack(nums, i+1, remain-nums[i])
    backtrack(nums, i+1, remain+nums[i])
}

// 注意：javascript 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

var backtrack = function(nums, i, remain) {
    if (i === nums.length) {
        return;
    }
    backtrack(nums, i + 1, remain - nums[i]);
    backtrack(nums, i + 1, remain + nums[i]);
}

树的高度就是 nums 的长度嘛，所以说时间复杂度就是这棵二叉树的节点数，为 O(2^N)，其实是非常低效的。

那么，这个问题如何用动态规划思想进行优化呢？

二、消除重叠子问题

动态规划之所以比暴力算法快，是因为动态规划技巧消除了重叠子问题。

如何发现重叠子问题？看是否可能出现重复的「状态」。对于递归函数来说，函数参数中会变的参数就是「状态」，对于 backtrack 函数来说，会变的参数为 i 和 remain。

前文动态规划之编辑距离说了一种一眼看出重叠子问题的方法，先抽象出递归框架：

void backtrack(int i, int remain) {
    backtrack(i + 1, remain - nums[i]);
    backtrack(i + 1, remain + nums[i]);
}

// 注意：cpp 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

void backtrack(int i, int remain) {
    backtrack(i + 1, remain - nums[i]);
    backtrack(i + 1, remain + nums[i]);
}

# 注意：python 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
# 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

def backtrack(i: int, remain: int):
    backtrack(i + 1, remain - nums[i])
    backtrack(i + 1, remain + nums[i])

// 注意：go 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

func backtrack(i int, remain int) {
    backtrack(i + 1, remain - nums[i])
    backtrack(i + 1, remain + nums[i])
}

// 注意：javascript 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

var backtrack = function(i, remain) {
    backtrack(i + 1, remain - nums[i]);
    backtrack(i + 1, remain + nums[i]);
}

举个简单的例子，如果 nums[i] = 0，会发生什么？

void backtrack(int i, int remain) {
    backtrack(i + 1, remain);
    backtrack(i + 1, remain);
}

// 注意：cpp 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

void backtrack(int i, int remain) {
    backtrack(i + 1, remain);
    backtrack(i + 1, remain);
}

# 注意：python 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
# 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

def backtrack(i: int, remain: int) -> None:
    backtrack(i + 1, remain)
    backtrack(i + 1, remain)

// 注意：go 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

func backtrack(i int, remain int) {
    backtrack(i + 1, remain)
    backtrack(i + 1, remain)
}

// 注意：javascript 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

var backtrack = function(i, remain) {
    backtrack(i + 1, remain);
    backtrack(i + 1, remain);
}

你看，这样就出现了两个「状态」完全相同的递归函数，无疑这样的递归计算就是重复的。这就是重叠子问题，而且只要我们能够找到一个重叠子问题，那一定还存在很多的重叠子问题。

因此，状态 (i, remain) 是可以用备忘录技巧进行优化的：

class Solution {
    int findTargetSumWays(int[] nums, int target) {
        if (nums.length == 0) return 0;
        return dp(nums, 0, target);
    }

    // 备忘录
    HashMap<String, Integer> memo = new HashMap<>();
    int dp(int[] nums, int i, int remain) {
        // base case
        if (i == nums.length) {
            if (remain == 0) return 1;
            return 0;
        }
        // 把它俩转成字符串才能作为哈希表的键
        String key = i + "," + remain;
        // 避免重复计算
        if (memo.containsKey(key)) {
            return memo.get(key);
        }
        // 还是穷举
        int result = dp(nums, i + 1, remain - nums[i]) + dp(nums, i + 1, remain + nums[i]);
        // 记入备忘录
        memo.put(key, result);
        return result;
    }
}

// 注意：cpp 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int target) {
        if (nums.size() == 0) return 0;
        return dp(nums, 0, target);
    }

private:
    // 备忘录
    unordered_map<string, int> memo;
    int dp(vector<int>& nums, int i, int remain) {
        // base case
        if (i == nums.size()) {
            if (remain == 0) return 1;
            return 0;
        }
        // 把它俩转成字符串才能作为哈希表的键
        string key = to_string(i) + "," + to_string(remain);
        // 避免重复计算
        if (memo.count(key)) {
            return memo[key];
        }
        // 还是穷举
        int result = dp(nums, i + 1, remain - nums[i]) + dp(nums, i + 1, remain + nums[i]);
        // 记入备忘录
        memo[key] = result;
        return result;
    }
};

# 注意：python 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
# 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

class Solution:
    def findTargetSumWays(self, nums: List[int], target: int) -> int:
        if len(nums) == 0:
            return 0
        # 备忘录
        memo = {}
        def dp(i, remain):
            # base case
            if i == len(nums):
                if remain == 0:
                    return 1
                return 0
            # 把它俩转成字符串才能作为哈希表的键
            key = str(i) + "," + str(remain)
            # 避免重复计算
            if key in memo:
                return memo[key]
            # 还是穷举
            result = dp(i + 1, remain - nums[i]) + dp(i + 1, remain + nums[i])
            # 记入备忘录
            memo[key] = result
            return result

        return dp(0, target)

// 注意：go 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

func findTargetSumWays(nums []int, target int) int {
    // 判断 nums 是否为空
    if len(nums) == 0 {
        return 0
    }
    // 备忘录
    memo := make(map[string]int)
    return dp(nums, 0, target, memo)
}

func dp(nums []int, i int, remain int, memo map[string]int) int {
    // 如果备忘录中存在，则返回
    key := fmt.Sprintf("%v,%v", i, remain)
    if val, ok := memo[key]; ok {
        return val
    }
    // 当 i 计算到底，根据 remain 是否为 0 返回 1 或 0
    if i == len(nums) {
        if remain == 0 {
            return 1
        }
        return 0
    }
    // 进行深度优先遍历，分别计算第 i 个数字 + 或 - 可以得到的结果
    result := dp(nums, i+1, remain-nums[i], memo) + dp(nums, i+1, remain+nums[i], memo)
    // 将结果加入备忘录
    memo[key] = result
    return result
}

// 注意：javascript 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

var findTargetSumWays = function(nums, target) {
    if (nums.length === 0) return 0;
    const memo = new Map();

    // 备忘录
    function dp(i, remain) {
        // base case
        if (i === nums.length) {
            if (remain === 0) return 1;
            return 0;
        }
        // 把它俩转成字符串才能作为哈希表的键
        const key = i + "," + remain;
        // 避免重复计算
        if (memo.has(key)) {
            return memo.get(key);
        }
        // 还是穷举
        const result = dp(i + 1, remain - nums[i]) + dp(i + 1, remain + nums[i]);
        // 记入备忘录
        memo.set(key, result);
        return result;
    }

    return dp(0, target);
};

🍭 代码可视化动画 🍭

以前我们都是用 Python 的元组配合哈希表 dict 来做备忘录的，其他语言没有元组，可以用把「状态」转化为字符串作为哈希表的键，这是一个常用的小技巧。

这个解法通过备忘录消除了很多重叠子问题，效率有一定的提升，但是这就结束了吗？

三、动态规划

其实，这个问题可以转化为一个子集划分问题，而子集划分问题又是一个典型的背包问题。动态规划总是这么玄学，让人摸不着头脑……

首先，如果我们把 nums 划分成两个子集 A 和 B，分别代表分配 + 的数和分配 - 的数，那么他们和 target 存在如下关系：

sum(A) - sum(B) = target
sum(A) = target + sum(B)
sum(A) + sum(A) = target + sum(B) + sum(A)
2 * sum(A) = target + sum(nums)

综上，可以推出 sum(A) = (target + sum(nums)) / 2，也就是把原问题转化成：nums 中存在几个子集 A，使得 A 中元素的和为 (target + sum(nums)) / 2？

类似的子集划分问题我们前文经典背包问题：子集划分讲过，现在实现这么一个函数：

/* 计算 nums 中有几个子集的和为 sum */
int subsets(int[] nums, int sum) {}

// 注意：cpp 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

// 计算 nums 中有几个子集的和为 sum
int subsets(vector<int>& nums, int sum) {}

# 注意：python 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
# 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

def subsets(nums: List[int], sum: int) -> int:
    # 计算 nums 中有几个子集的和为 sum

// 注意：go 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

// 计算 nums 中有几个子集的和为 sum
func subsets(nums []int, sum int) int {}

// 注意：javascript 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

/*
计算 nums 中有几个子集的和为 sum
*/
var subsets = function(nums, sum) {}

然后，可以这样调用这个函数：

int findTargetSumWays(int[] nums, int target) {
    int sum = 0;
    for (int n : nums) sum += n;
    // 这两种情况，不可能存在合法的子集划分
    if (sum < Math.abs(target) || (sum + target) % 2 == 1) {
        return 0;
    }
    return subsets(nums, (sum + target) / 2);
}

// 注意：cpp 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

int findTargetSumWays(vector<int>& nums, int target) {
    int sum = 0;
    for (int n : nums) sum += n;
    // 这两种情况，不可能存在合法的子集划分
    if (sum < abs(target) || (sum + target) % 2 == 1) {
        return 0;
    }
    return subsets(nums, (sum + target) / 2);
}

# 注意：python 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
# 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

def findTargetSumWays(nums: List[int], target: int) -> int:
    sum = 0
    for n in nums:
        sum += n
    # 这两种情况，不可能存在合法的子集划分
    if sum < abs(target) or (sum + target) % 2 == 1:
        return 0
    return subsets(nums, (sum + target) // 2)

// 注意：go 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

// numDistinct计算子序列数
// s 和 t 均为一个字符串
// 采用动态规划算法
int numDistinct(String s, String t) {
    int m = s.length();
    int n = t.length();
    if (m < n) {
        return 0;
    }
    int[][] dp = new int[m+1][n+1];
    for (int i = 0; i <= m; i++) {
        dp[i][n] = 1;
    }
    for (int i = m - 1; i >= 0; i--) {
        char sChar = s.charAt(i);
        for (int j = n - 1; j >= 0; j--) {
            char tChar = t.charAt(j);
            if (sChar == tChar) {
                dp[i][j] = dp[i+1][j+1] + dp[i+1][j];
            } else {
                dp[i][j] = dp[i+1][j];
            }
        }
    }
    return dp[0][0];
}

// 注意：javascript 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

var findTargetSumWays = function(nums, target) {
    var sum = 0;
    for (var i = 0; i < nums.length; i++) {
        sum += nums[i];
    }
    // 这两种情况，不可能存在合法的子集划分
    if (sum < Math.abs(target) || (sum + target) % 2 === 1) {
        return 0;
    }
    return subsets(nums, (sum + target) / 2);
};

好的，变成背包问题的标准形式：

有一个背包，容量为 sum，现在给你 N 个物品，第 i 个物品的重量为 nums[i - 1]（注意 1 <= i <= N），每个物品只有一个，请问你有几种不同的方法能够恰好装满这个背包？

现在，这就是一个正宗的动态规划问题了，下面按照我们一直强调的动态规划套路走流程：

第一步要明确两点，「状态」和「选择」。

对于背包问题，这个都是一样的，状态就是「背包的容量」和「可选择的物品」，选择就是「装进背包」或者「不装进背包」。

第二步要明确 dp 数组的定义。

按照背包问题的套路，可以给出如下定义：

dp[i][j] = x 表示，若只在前 i 个物品中选择，若当前背包的容量为 j，则最多有 x 种方法可以恰好装满背包。

翻译成我们探讨的子集问题就是，若只在 nums 的前 i 个元素中选择，若目标和为 j，则最多有 x 种方法划分子集。

根据这个定义，显然 dp[0][..] = 0，因为没有物品的话，根本没办法装背包；但是 dp[0][0] 应该是个例外，因为如果背包的最大载重为 0，「什么都不装」也算是一种装法，即 dp[0][0] = 1。

可能有些看过前文 0-1 背包问题和完全背包问题这两篇背包问题的文章之后会有疑问，为什么 base case 不是 dp[..][0] = 1 呢？即背包容量为 0 时，只有「什么都不装」这一种装法。这里不能这样初始化，是因为本题 nums 数组中的元素是可能为 0 的，那么背包容量为 0 时，「什么都不装」可能就不是唯一的装法了，而需要在状态转移的过程中具体去计算。

我们所求的答案就是 dp[N][sum]，即使用所有 N 个物品，有几种方法可以装满容量为 sum 的背包。

第三步，根据「选择」，思考状态转移的逻辑。

回想刚才的 dp 数组含义，可以根据「选择」对 dp[i][j] 得到以下状态转移：

如果不把 nums[i] 算入子集，或者说你不把这第 i 个物品装入背包，那么恰好装满背包的方法数就取决于上一个状态 dp[i-1][j]，继承之前的结果。

如果把 nums[i] 算入子集，或者说你把这第 i 个物品装入了背包，那么只要看前 i - 1 个物品有几种方法可以装满 j - nums[i-1] 的重量就行了，所以取决于状态 dp[i-1][j-nums[i-1]]。

注意我们说的 i 是从 1 开始算的，而数组 nums 的索引时从 0 开始算的，所以 nums[i-1] 代表的是第 i 个物品的重量，j - nums[i-1] 就是背包装入物品 i 之后还剩下的容量。

由于 dp[i][j] 为装满背包的总方法数，所以应该以上两种选择的结果求和，得到状态转移方程：

dp[i][j] = dp[i-1][j] + dp[i-1][j-nums[i-1]];

然后，根据状态转移方程写出动态规划算法：

/* 计算 nums 中有几个子集的和为 sum */
int subsets(int[] nums, int sum) {
    int n = nums.length;
    int[][] dp = new int[n + 1][sum + 1];
    // base case
    dp[0][0] = 1;
    
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j <= sum; j++) {
            if (j >= nums[i-1]) {
                // 两种选择的结果之和
                dp[i][j] = dp[i-1][j] + dp[i-1][j-nums[i-1]];
            } else {
                // 背包的空间不足，只能选择不装物品 i
                dp[i][j] = dp[i-1][j];
            }
        }
    }
    return dp[n][sum];
}

// 注意：cpp 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

int subsets(vector<int>& nums, int sum) {
    int n = nums.size();
    vector<vector<int>> dp(n + 1, vector<int>(sum + 1, 0));
    // base case
    dp[0][0] = 1;

    for (int i = 1; i <= n; i++) {
        for (int j = 0; j <= sum; j++) {
            if (j >= nums[i-1]) {
                // 两种选择的结果之和
                dp[i][j] = dp[i-1][j] + dp[i-1][j-nums[i-1]];
            } else {
                // 背包的空间不足，只能选择不装物品 i
                dp[i][j] = dp[i-1][j];
            }
        }
    }
    return dp[n][sum];
}

# 注意：python 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
# 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

def subsets(nums: List[int], sum: int) -> int:
    n = len(nums)
    dp = [[0]*(sum+1) for _ in range(n+1)]
    # base case
    dp[0][0] = 1
    
    for i in range(1, n+1):
        for j in range(sum+1):
            if j >= nums[i-1]:
                # 两种选择的结果之和
                dp[i][j] = dp[i-1][j] + dp[i-1][j-nums[i-1]]
            else:
                # 背包的空间不足，只能选择不装物品 i
                dp[i][j] = dp[i-1][j]
    return dp[n][sum]

// 注意：go 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

func subsets(nums []int, sum int) int {
    n := len(nums)
    dp := make([][]int, n+1)
    for i := range dp {
        dp[i] = make([]int, sum+1)
    }
    // base case
    dp[0][0] = 1
    
    for i := 1; i <= n; i++ {
        for j := 0; j <= sum; j++ {
            if j >= nums[i-1] {
                // 两种选择的结果之和
                dp[i][j] = dp[i-1][j] + dp[i-1][j-nums[i-1]]
            } else {
                // 背包的空间不足，只能选择不装物品 i
                dp[i][j] = dp[i-1][j]
            }
        }
    }
    return dp[n][sum]
}

// 注意：javascript 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

var subsets = function(nums, sum) {
    var n = nums.length;
    var dp = new Array(n + 1).fill().map(() => new Array(sum + 1).fill(0));
    // base case
    dp[0][0] = 1;

    for (var i = 1; i <= n; i++) {
        for (var j = 0; j <= sum; j++) {
            if (j >= nums[i-1]) {
                // 两种选择的结果之和
                dp[i][j] = dp[i-1][j] + dp[i-1][j-nums[i-1]];
            } else {
                // 背包的空间不足，只能选择不装物品 i
                dp[i][j] = dp[i-1][j];
            }
        }
    }
    return dp[n][sum];
};

然后，发现这个 dp[i][j] 只和前一行 dp[i-1][..] 有关，那么肯定可以优化成一维 dp：

/* 计算 nums 中有几个子集的和为 sum */
int subsets(int[] nums, int sum) {
    int n = nums.length;
    int[] dp = new int[sum + 1];
    // base case
    dp[0] = 1;
    
    for (int i = 1; i <= n; i++) {
        // j 要从后往前遍历
        for (int j = sum; j >= 0; j--) {
            // 状态转移方程
            if (j >= nums[i-1]) {
                dp[j] = dp[j] + dp[j-nums[i-1]];
            } else {
                dp[j] = dp[j];
            }
        }
    }
    return dp[sum];
}

// 注意：cpp 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

/* 计算nums中有几个子集的和为sum */
int subsets(vector<int>& nums, int sum) {
    int n = nums.size();
    vector<int> dp(sum + 1);
    // base case
    dp[0] = 1;
    
    for (int i = 1; i <= n; i++) {
        // j 要从后往前遍历
        for (int j = sum; j >= 0; j--) {
            // 状态转移方程
            if (j >= nums[i-1]) {
                dp[j] = dp[j] + dp[j-nums[i-1]];
            } else {
                dp[j] = dp[j];
            }
        }
    }
    return dp[sum];
}

# 注意：python 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
# 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

def subsets(nums: List[int], sum: int) -> int:
    n = len(nums)
    dp = [0] * (sum + 1)
    # base case
    dp[0] = 1
    
    for i in range(1, n + 1):
        # j 要从后往前遍历
        for j in range(sum, -1, -1):
            # 状态转移方程
            if j >= nums[i-1]:
                dp[j] += dp[j-nums[i-1]]
    
    return dp[sum]

// 注意：go 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

func subsets(nums []int, sum int) int {
    n := len(nums)
    dp := make([]int, sum+1)
    // base case
    dp[0] = 1
    
    for i := 1; i <= n; i++ {
        // j 要从后往前遍历
        for j := sum; j >= 0; j-- {
            // 状态转移方程
            if j >= nums[i-1] {
                dp[j] = dp[j] + dp[j-nums[i-1]]
            } else {
                dp[j] = dp[j]
            }
        }
    }
    return dp[sum]
}

// 注意：javascript 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

var subsets = function(nums, sum) {
    var n = nums.length;
    var dp = new Array(sum + 1).fill(0);
    // base case
    dp[0] = 1;

    for (var i = 1; i <= n; i++) {
        // j 要从后往前遍历
        for (var j = sum; j >= 0; j--) {
            // 状态转移方程
            if (j >= nums[i-1]) {
                dp[j] = dp[j] + dp[j-nums[i-1]];
            } else {
                dp[j] = dp[j];
            }
        }
    }
    return dp[sum];
};

对照二维 dp，只要把 dp 数组的第一个维度全都去掉就行了，唯一的区别就是这里的 j 要从后往前遍历，原因如下：

因为二维压缩到一维的根本原理是，dp[j] 和 dp[j-nums[i-1]] 还没被新结果覆盖的时候，相当于二维 dp 中的 dp[i-1][j] 和 dp[i-1][j-nums[i-1]]。

那么，我们就要做到：在计算新的 dp[j] 的时候，dp[j] 和 dp[j-nums[i-1]] 还是上一轮外层 for 循环的结果。

如果你从前往后遍历一维 dp 数组，dp[j] 显然是没问题的，但是 dp[j-nums[i-1]] 已经不是上一轮外层 for 循环的结果了，这里就会使用错误的状态，当然得不到正确的答案。

现在，这道题算是彻底解决了。

总结一下，回溯算法虽好，但是复杂度高，即便消除一些冗余计算，也只是「剪枝」，没有本质的改进。而动态规划就比较玄学了，经过各种改造，从一个加减法问题变成子集问题，又变成背包问题，经过各种套路写出解法，又搞出空间压缩，还得反向遍历。

现在我都搞不清楚自己是来干嘛的了。嗯，这也许就是动态规划的魅力吧。

接下来可阅读：

分治算法：运算优先级

引用本文的题目

安装我的 Chrome 刷题插件点开下列题目可直接查看解题思路：

LeetCode	力扣
-	剑指 Offer II 102. 加减的目标值

引用本文的文章

分治算法详解：运算优先级

＿＿＿＿＿＿＿＿＿＿＿＿＿

《labuladong 的算法小抄》已经出版，关注公众号查看详情；后台回复关键词「进群」可加入算法群；回复「全家桶」可下载配套 PDF 和刷题全家桶：

共同维护高质量学习环境，评论礼仪见这里，违者直接拉黑不解释