寻找和为定值的多个数

问题：
1. 找出一个序列中和为sum的两个数
2. 找出一个序列中和为sum的多个数（不限个数）
3. 找出一个序列中和为sum的4个数

解析：

1. 找出一个序列中和为sum的两个数

• 将序列排序
• 用左右2个指针指向序列的头部和尾部
• 如果当前2个指针指向数的当前和等于sum，则这两个数是一个结果；如果当前和小于sum，说明当前和应该大一点，则将左指针右移 1 位；如果当前和大于sum，说明当前和应该小一点，则将右指针左移 1 位

2. 找出一个序列中和为sum的多个数（不限个数）

0-1 背包问题，考虑是否取第 n 个数可以转化为只和前 n-1 个数有关的问题

• 取第 n 个数，则问题转为“对 n - 1 个数中，找出和为 sum - input[n-1]的数”（第 n 个数的下标是 n-1）:sumOfkNumber(sum - input[n-1], n - 1)；
• 不取第 n 个数，则问题转为“对 n - 1 个数中，找出和为 sum的数”:sumOfkNumber(sum, n - 1)；

3. 找出一个序列中和为sum的4个数

针对找出和为sum的多个数，控制加入数的数量，只有恰好有 4 个数，才看做一个结果。

#include <iostream>
#include <vector>
#include <algorithm>
#include <stdlib.h>
using namespace std;
class Solution {
public:
    // 两个数
    void PrintTwoNumWithSum(vector<int> input, int sum)
    {
        if (input.size() < 1 || sum < 0)
            return;
        int i = 0;
        int j = input.size() - 1;
        while (i < j) {
            int curSum = input[i] + input[j];
            if (curSum == sum) {
                cout << input[i] << " " << input[j] << endl;
                ++i;
            } else if (curSum < sum) {
                ++i;
            }   else {
                --j;
            }
        }
    }
    // 多个数
    void PrintNNumWithSum(vector<int> &input, int sum) {
        if (input.size() < 1 || sum < 0)
            return;
        vector<int> result;
        PrintNNumWithSumHelper(input, input.size()-1, sum, result);
    }
    // 四个数
    void Print4NumsWithSum(vector<int> &input, int sum, int m) {
        if (input.size() < 1 || sum < 0)
            return;
        vector<int> result;
        Print4NumWithSumHelper(input, input.size() - 1, sum, m, result);
    }
private:
    // 多个数
    void PrintNNumWithSumHelper(vector<int> &input, int n, int sum, vector<int> &result) {
        if (n < 0 || sum < 0)
            return;
        if (sum == input[n]) {
            cout << input[n] << " ";
            if (result.size() > 0) {
                for (int i = result.size() - 1; i >= 0; i--) {
                    cout << result[i] << " ";
                }
            }
            cout << endl;
        }
        result.push_back(input[n]);
        PrintNNumWithSumHelper(input, n - 1, sum - input[n], result);
        result.pop_back();
        PrintNNumWithSumHelper(input, n - 1, sum, result);
    }
    // 四个数
    void Print4NumWithSumHelper(vector<int> &input, int n, int sum, int m, vector<int> &result) {
        if (n < 0 || sum < 0 || result.size() == m)
            return;
        if (result.size() == m-1 && sum == input[n]) {
            cout << input[n] << " ";
            if (result.size() > 0) {
                for (int i = result.size() - 1; i >= 0; i--) {
                    cout << result[i] << " ";
                }
            }
            cout << endl;
        }
        result.push_back(input[n]);
        Print4NumWithSumHelper(input, n - 1, sum - input[n], m, result);
        result.pop_back();
        Print4NumWithSumHelper(input, n - 1, sum, m, result);
    }
};

int main()
{
    vector<int> input;
    for (int i = 0; i < 50; i++) {
        input.push_back(i + 1);
    }
    sort(input.begin(), input.end());
    Solution sol;
    int sum = 20;
    cout << "======打印和为 " << sum <<" 的两个数=======" << endl;
    sol.PrintTwoNumWithSum(input, sum);
    cout << "======打印和为 " << sum << " 的数=======" << endl;
    sol.PrintNNumWithSum(input, sum);
    cout << "======打印和为 " << sum << " 的4个数=======" << endl;
    sol.Print4NumsWithSum(input, sum, 4);
}

参考资料：https://github.com/julycoding/The-Art-Of-Programming-By-July/blob/master/ebook/zh/02.03.md