文章目录

• 子集(78)
• • 代码解答
• 目标和(494)
• • 代码解答

子集(78)

这道题要求我们返回指定数组的所有子集,而且要求不能包含重复的子集。
因此这道题我们依旧采用回溯算法
(一): 我们先定义结果:

List> res = new ArrayList<>();
List list = new ArrayList<>();

每个子集都是一个list集合，我们没获取到一个子集就对应一个list集合，同时我们就将这list集合加入到res中去，这里我们定义一个start指针从数组的索引0开始，最后只需要返回一个res即可。

    public List> subsets(int[] nums) {res.add(new ArrayList(list));helper(nums,0);return res;}

接着我们只需要编写回溯部分的代码，根据回溯的模板：
(一):当start指针到达数组的边界时就表示结束，这也是递归的终止条件。

        if(start >= nums.length){return;}

(二):for循环体，我们从start的位置开始遍历，将每个元素也就是nums[i]，加入到list集合中去,当我们没获取到一个list集合就将list集合加入到res中。因为每个元素都不能重复，因此我们下次递归的start的值就是i+1,最后回退到最初的list就完成了。

        for(int i=start;ilist.add(nums[i]);res.add(new ArrayList(list));helper(nums,i+1);list.remove(list.size()-1);}

代码解答

class Solution {List> res = new ArrayList<>();List list = new ArrayList<>();public List> subsets(int[] nums) {res.add(new ArrayList(list));helper(nums,0);return res;}public void helper(int[] nums,int start){if(start >= nums.length){return;}for(int i=start;ilist.add(nums[i]);res.add(new ArrayList(list));helper(nums,i+1);list.remove(list.size()-1);}}
}

目标和(494)

这道题让我们从nums中选择数字，并且在前面加上（-）或者（+）使得最后的和为target。
我们将数组的长度len和目标值target放到全局变量的位置，方便后期的调用，同时定义一个结果res。

    int len = 0;int target = 0;int res = 0;public int findTargetSumWays(int[] nums, int target) {this.len = nums.length;this.target = target;back(nums,0,0);return res;}

我们在back方法里面传入的参数分别为数组nums，和sum，指针index。
当指针达到数组的长度len的时候我们就判断这时的sum和target是否相等，
如果相等就res结果集+1，如果不相等就直接退出，因为已经到头了。
接着我们不断递归+ 和 - 两种

        // 如果整个数组元素都用上了if(index == len){// 如果是target，那么次数++if(sum == target){res++;}// 如果不是直接返回return;}// +back(nums,sum + nums[index],index + 1);// -back(nums,sum - nums[index],index + 1);

代码解答

class Solution {// 如果使用回溯暴力搜索，每个数组元素无非 + -，时间复杂度为2 ^ nint len = 0;int target = 0;int res = 0;public int findTargetSumWays(int[] nums, int target) {this.len = nums.length;this.target = target;back(nums,0,0);return res;}private void back(int[] nums, int sum, int index){// 如果整个数组元素都用上了if(index == len){// 如果是target，那么次数++if(sum == target){res++;}// 如果不是直接返回return;}// +back(nums,sum + nums[index],index + 1);// -back(nums,sum - nums[index],index + 1);}
}