美文网首页
Leetcode 39 组合总和

Leetcode 39 组合总和

作者: itbird01 | 来源:发表于2022-01-01 00:23 被阅读0次
    题目.png

    题意:给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ,找出 candidates 中可以使数字和为目标数 target 的 所有不同组合 ,并以列表形式返回。你可以按 任意顺序 返回这些组合。
    candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同,则两种组合是不同的。
    对于给定的输入,保证和为 target 的不同组合数少于 150 个。

    解法:
    1.审题可知,其实就是回溯算法的应用
    2.排列组合的回溯算法实现
    3.涉及到重复元素,所以先给数组排序
    4.涉及到剪枝,我们由3已知,数组为有序数组,所以遍历过的数字不再遍历,所以记录每次遍历的start位置,用于剪枝

    ##解法1
    import java.util.ArrayList;
    import java.util.Arrays;
    import java.util.List;
    
    class Solution {
        List<List<Integer>> ans = new ArrayList<List<Integer>>();
        List<Integer> temp = new ArrayList<Integer>();
    
        public List<List<Integer>> combinationSum(int[] candidates, int target) {
            Arrays.sort(candidates);
            backSearch(0, 0, candidates, target);
            return ans;
        }
    
        private void backSearch(int cur, int start, int[] nums, int target) {
            if (cur == target) {
                ans.add(new ArrayList<Integer>(temp));
                return;
            }
    
            if (cur > target) {
                return;
            }
    
            for (int i = start; i < nums.length; i++) {
                temp.add(nums[i]);
                cur += nums[i];
                backSearch(cur, i, nums, target);
                temp.remove(temp.size() - 1);
                cur -= nums[i];
            }
        }
    }
    

    相关文章

      网友评论

          本文标题:Leetcode 39 组合总和

          本文链接:https://www.haomeiwen.com/subject/hrwiqrtx.html