39. 组合总和
剪枝优化
如果已经知道下一层的sum会大于target,就没有必要进入下一层递归了。<br>对总集合排序之后,如果下一层的sum(就是本层的 sum + candidates[i])已经大于target,就可以结束本轮for循环的遍历。<br>
时间复杂度:<span class="equation-text" contenteditable="false" data-index="0" data-equation="O(n * 2^n)"><span></span><span></span></span>,注意这只是复杂度的上界,因为剪枝的存在,真实的时间复杂度远小于此<br>空间复杂度:<span class="equation-text" contenteditable="false" data-index="1" data-equation="O(target)"><span></span><span></span></span>