1.是否划分成2个相等和的子数组，转化为0-1背包问题，何为sum/2，二重循环从大到小遍历
#include <stdio.h>#include <iostream>#include<vector>using namespace std;bool canPartion(vector<int>nums) { int sum = 0; for (int i = 0; i < nums.size(); i++) { sum += nums[i]; } if (sum % 2 == 1) { return false; } int target = sum / 2; vector<int> dp(target + 1, 0); for (int i = 0; i < nums.size(); i++) { for (int j = target; j >= nums[i]; j--) { dp[j] = max(dp[j], dp[j-nums[i]] + nums[i]); } } std::cout << dp[target] << " " << target << endl; return dp[target] == target;}int main(){ vector<int> nums = {1, 5, 11, 5}; cout << canPartion(nums) << endl; return 0;}2。是否划分成k个和雷同数组，间接递归
#include <stdio.h>#include <iostream>#include<vector>#include<algorithm>using namespace std;bool dfs(vector<int> &nums, vector<int> &visited, int start, int k, int cur_sum, int target) { if (k == 1) return true; if (target < cur_sum) return false; if (target == cur_sum) return dfs(nums, visited, 0, k - 1, 0, target); for (int i = start; i < nums.size(); i++) { if (visited[i]) continue; visited[i] = 1; if(dfs(nums, visited, i + 1, k, cur_sum + nums[i], target)) { return true; } visited[i] = 0; } return false;}int main(){ vector<int> nums = {4, 3, 2, 3, 5, 2, 1}; int sum = 0; for (auto num : nums) { sum += num; } int k = 4; if (sum % k !=0 ) { cout <<"error" <<endl; return 0; } std::sort(nums.begin(), nums.end(), greater<int>()); vector<int> visited(nums.size(), 0); cout << dfs(nums, visited, 0, k, 0, sum / k) << " " << sum / k <<endl; return 0;}