正规免费发布信息网站,网站被黑能查到是谁做的吗,浙江省财务开发公司官网,生活中优秀的产品设计组合总和
问题描述
给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target #xff0c;找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 #xff0c;并以列表形式返回。你可以按 任意顺序 返回这些组合。candidates 中的 同一个 数字可以 无限…组合总和
问题描述
给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target 找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 并以列表形式返回。你可以按 任意顺序 返回这些组合。candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同则两种组合是不同的。 对于给定的输入保证和为 target 的不同组合数少于 150 个。详见leetcode39
问题分析
我们可以从candidates[0]开始不断选取candidates[0]直至target-candidates[0]0,如果等于0则我们得到一个满足条件的组合否则回退一步去掉一个candidates[0]添加一个candidates[1]如此不断进行下去满足局部枚举➕递归放下前任我门可以使用回溯模板来解决。
代码实现
public ListListInteger combinationSum(int[] candidates, int target) {ListInteger numList new ArrayList();ListListInteger resultList new ArrayList();combinationSum(candidates,target,0,numList,resultList);return resultList;
}public void combinationSum(int[] candidates, int target,int index,ListInteger numList,ListListInteger resultList){if(target0){return;}if(target0){resultList.add(new ArrayList(numList));return;}for(int iindex;icandidates.length;i){numList.add(candidates[i]);combinationSum(candidates,target-candidates[i],i,numList,resultList);numList.remove(numList.size()-1);}
}全排列
问题描述
给定一个不含重复数字的数组 nums 返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。
问题分析
排列与组合类似只是重复元素可以按照不同顺序成为不同的排列我们不再是按顺序的取而是定义一个used数组判断给定数组的元素是否被使用。当我们的排列结果中的元素与给定数组个数相同时即得到一个排列添加到结果数组中。
代码实现
public ListListInteger permute(int[] nums) {ListListInteger res new ArrayList();LinkedListInteger ans new LinkedList();boolean[] used new boolean[nums.length];permute(res,ans,used,nums);return res;
}
public void permute(ListListInteger res,LinkedListInteger ans,boolean[] used,int[] nums){if(ans.size()nums.length){res.add(new ArrayList(ans));return;}for(int i0;inums.length;i){if(used[i]){continue;}used[i] true;ans.add(nums[i]);permute(res,ans,used,nums);ans.removeLast();used[i] false;}
}
