组合工具函数：从数组a从位置i开始选取k个数
*/
void combinationUtil(int a[], int n, int i, int k, int *select)
{
if (i > n) return; //位置超出数组范围直接返回，否则非法访问会出段错误
if (k == 0) { //选取完了，输出选取的数字
int j;
for (j = 0; j < n; j++) {
if (select[j])
printf("%d ", a[j]);
}
printf("\n");
} else {
select[i] = 1;
combinationUtil(a, n, i+1, k-1, select); //第i个数字被选取，从后续i+1开始选取k-1个数
select[i] = 0;
combinationUtil(a, n, i+1, k, select); //第i个数字不选，则从后续i+1位置开始还要选取k个数
}
}
复制代码
这个比较简单，代码如下：
void reversePrint(const char *str) { if (!*str) return; reversePrint(str + 1); putchar(*str);}
复制代码
链表逆序通常我们会用迭代的方式实现，但是如果要显得特立独行一点，可以使用递归，如下，代码请见仓库的 aslist 目录。
/** * 链表逆序，递归实现。 */ ListNode *listReverseRecursive(ListNode *head) { if (!head || !head->next) { return head; } ListNode *reversedHead = listReverseRecursive(head->next); head->next->next = head; head->next = NULL; <span>return</span> reversedHead;}
复制代码
背包问题包括0-1背包问题、完全背包问题、部分背包问题等多种变种。其中，最简单的是部分背包问题，它可以采用贪心法来解决，而其他几种背包问题往往需要动态规划来求解。本文主要来源于《背包问题九讲》，我选择了比较简单的0-1背包问题和完全背包问题进行汇总。同时给出实现代码，如有错误，请各位大虾指正。本文代码在 这里。
1.部分背包问题部分背包问题描述： 有 N 件物品和一个容量为 C 的背包。第 i 件物品的重量是 w[i]，价值是 v[i]。求解将哪些物品装入背包可使价值总和最大。注意这里不要求把物品整个装入，可以只装入一个物品的部分。
解法： 部分背包问题常采用贪心算法来解决，先对每件物品计算其每单位重量价值 v[i]/w[i]，然后从具有最大单位价值的物品开始拿，然后拿第二大价值的物品，直到装满背包。按照这种贪心策略拿到的必然是价值总和最大，这个比较简单，实现代码就略去了。
2. 0-1背包问题 0-1背包问题描述有 N 件物品和一个容量为 C 的背包。第 i 件物品的重量是 w[i]，价值是v[i]。求解将哪些物品装入背包可使价值总和最大。注意物品只能要么拿要么不拿，这也正是 0-1 的意义所在。可以把部分背包问题看作是拿金粉，而 0-1 背包问题则是拿金块，一个可分，一个不可分。
分析这是最基础的背包问题，特点是：每种物品仅有一件，可以选择放或不放。 用子问题定义状态：即 f[i][w] 表示前 i 件物品恰放入一个容量为 c 的背包可以获得的最大价值。则其状态转移方程便是：
f[i][c] = max{f[i-1][c], f[i-1][c-w[i]]+v[i]} 复制代码这个方程非常重要，基本上所有跟背包相关的问题的方程都是由它衍生出来的。所以有必要将它详细解释一下：将前 i 件物品放入容量为 c 的背包中 这个子问题，若只考虑第i件物品的策略（放或不放），那么就可以转化为一个只牵扯前 i-1 件物品的问题。
如果不放第 i 件物品，那么问题就转化为 前 i-1 件物品放入容量为 v 的背包中，价值为 f[i-1][c]；
如果放第i件物品，那么问题就转化为 前 i-1 件物品放入剩下的容量为 c-w[i] 的背包中，此时能获得的最大价值就是 f[i-1][c-w[i]]再加上通过放入第 i 件物品获得的价值 v[i]。
优化空间复杂度以上方法的时间和空间复杂度均为 O(CN)，其中时间复杂度应该已经不能再优化了，但空间复杂度却可以优化到 O(N)。 由于在计算 f[i][c] 的时候，我们只需要用到 f[i-1][c] 和 f[i-1][c-w[i]]，所以完全可以通过一维数组保存它们的值，这里用到的小技巧就是需要从 c=C...0 开始反推，这样就能保证在求 f[c] 的时候 f[c-w[i]] 保存的是 f[i-1][c-w[i]] 的值。注意，这里不能从 c=0...C 这样顺推，因为这样会导致 f[c-w[i]] 的值是 f[i][c-w[i]] 而不是 f[i-1][c-w[i]。这里可以优化下界，其实只需要从 c=C...w[i] 即可，可以避免不需要的计算。伪代码如下所示：
for i=0..N-1 for c=C..w[i] f[c]=max{f[c],f[c-w[i]]+v[i]}; 复制代码