题目描述

  1. 给定一个整数数组  nums 和一个正整数 k，找出是否有可能把这个数组分成 k 个非空子集，其总和都相等。
  3. 示例 1：
  5. 输入： nums = [4, 3, 2, 3, 5, 2, 1], k = 4
  6. 输出： True
  7. 说明： 有可能将其分成 4 个子集（5），（1,4），（2,3），（2,3）等于总和。
  8. 示例 2:
  10. 输入: nums = [1,2,3,4], k = 3
  11. 输出: false
  14. 提示：
  16. 1 <= k <= len(nums) <= 16
  17. 0 < nums[i] < 10000
  18. 每个元素的频率在 [1,4] 范围内

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/partition-to-k-equal-sum-subsets 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解题思路

这种求解问题，首先看了一下感觉不能用动态规划来做，因为不具有共同子问题和最优子结构
那还是老老实实先从排列组合的思路来看，计算机比人强就强在，他善于辛辛苦苦的按照规则进行计算
首先啊，我们可以观察发现，nums数组总和应该是可以知道的，先遍历一遍求和即可，然后我们可以发现，k知道之后，就可以知道我们要去凑的那个子集的和为多少了。
就698. 划分为k个相等的子集TodoDP状态压缩 - 图1

代码实现

  1. class CQueue {
  2.     stack<int> A,B;
  3. public:
  4.     CQueue() {
  5.         //stack<int> A,B;
  6.     }
  8.     void appendTail(int value) {
  9.         A.push(value);
  10.     }
  12.     int deleteHead() {
  13.         int temp_result;
  14.         if(B.empty()){
  15.             if(A.empty())
  16.                 return -1;
  17.             else{
  18.                 while(A.empty()==0){
  19.                     B.push(A.top());
  20.                     A.pop();
  21.                 }
  22.                 temp_result = B.top();
  23.                 B.pop();
  24.                 return temp_result;
  25.             }
  26.         }
  27.         else{
  28.             temp_result = B.top();
  29.             B.pop();
  30.             return temp_result;
  31.         }
  32.     }
  33. };
  35. /**
  36.  * Your CQueue object will be instantiated and called as such:
  37.  * CQueue* obj = new CQueue();
  38.  * obj->appendTail(value);
  39.  * int param_2 = obj->deleteHead();
  40.  */

[

](https://www.zhihu.com/question/38842804/answer/78413820)