一: 解题思路
Time:O(n^(target/min)),Space:O(target/min) , 其中 n 为数组长度, min 是数组中的最小值.
二: 完整代码示例 (C++ 版和 Java 版)
C++:
- class Solution
- {
- private:
- void comSum(vector<int>& nums, int start, int target, vector<int>& elem, vector<vector<int>>& result)
- {
- if (target == 0)
- {
- result.push_back(elem);
- return;
- }
- if (target <0) return;
- for (int i = start; i < nums.size(); i++)
- {
- elem.push_back(nums[i]);
- comSum(nums,i,target-nums[i],elem,result);
- elem.pop_back();
- }
- }
- public:
- vector<vector<int>> combinationSum(vector<int>& candidates, int target)
- {
- vector<int> elem;
- vector<vector<int>> result;
- comSum(candidates,0,target,elem,result);
- return result;
- }
- };
Java:
- class Solution
- {
- private void comSum(int[] nums,int start,int target,List<Integer> elem,List<List<Integer>> result)
- {
- if(target==0)
- {
- result.add(new ArrayList<>(elem));
- return;
- }
- if(target<0) return;
- for(int i=start;i<nums.length;i++)
- {
- elem.add(nums[i]);
- comSum(nums,i,target-nums[i],elem,result);
- elem.remove(elem.size()-1);
- }
- }
- public List<List<Integer>> combinationSum(int[] candidates, int target)
- {
- List<Integer> elem=new ArrayList<>();
- List<List<Integer>> result=new ArrayList<>();
- comSum(candidates,0,target,elem,result);
- return result;
- }
- }
来源: http://www.bubuko.com/infodetail-3508252.html