保定网站制作推广,大理微网站建设,大连网站建设佳熙科技公司,第一ppt网站官网这道题如果用暴力法几乎是不可能解出来的#xff0c;因为情况太复杂了#xff0c;但是一旦用上递归回溯就会轻松很多#xff0c;先上代码#xff1a;
class Solution {ListListInteger result new ArrayListListInteger();ListInteg… 这道题如果用暴力法几乎是不可能解出来的因为情况太复杂了但是一旦用上递归回溯就会轻松很多先上代码
class Solution {ListListInteger result new ArrayListListInteger();ListInteger list new ArrayListInteger();public ListListInteger subsets(int[] nums) {dfs(0,nums);return result;}public void dfs(int cur, int[] nums){if(cur nums.length){result.add(new ArrayListInteger(list));return;}list.add(nums[cur]);dfs(cur1, nums);list.remove(list.size()-1);dfs(cur1, nums);}
}
对于数组中每个元素其无非就两种状态加入这个数组或者不加入这个数组所以我们创建一个递归方法dfs(int cur, int[] nums),cur就是我们当前处理的这个元素的下标。
if(cur nums.length){result.add(new ArrayListInteger(list));return;}
如果这个下标等于数组长度说明数组中的所有元素都判断过了可以把这个数组放进答案里了但是我们不能把list放进去因为这个list是全局的dfs方法都在动这个list后面的dfs会修改list如果是放list那么result里面就是全部一样的list并且是最后改完的list也就是空的list因为最后一个递归是所有元素都是不添加的情况。所以这里用的是result.add(new ArrayListInteger(list));把list的副本添加进了result这个副本不是指向list而是一个新的对象通过这个new也可以看出。
添加nums[cur]的情况:
list.add(nums[cur]);
dfs(cur1, nums);
不添加nums[cur]的情况 list.remove(list.size()-1);dfs(cur1, nums);
nums[cur]的情况判断完了后面dfs(cur1,nums)判断nums[cur1]的情况。
还有一种方法是迭代法
class Solution {ListListInteger result new ArrayListListInteger();ListInteger list new ArrayListInteger();public ListListInteger subsets(int[] nums) {int n nums.length;for(int mask 0;mask Math.pow(2,n);mask){list.clear();for(int i 0;in;i){if((mask (1 i)) ! 0){list.add(nums[i]);}}result.add(new ArrayListInteger(list));}return result;}
}
就用对于数组中的任一元素用01表示它的状态0表示不在数组中1表示在数组中。假设数组长度为n那么每一个n位的的01序列都表示一种情况一共有2的n次方个序列分别是0到2的n次方减1那么我们只需要每一种情况都用一个list放数据就好了对于每一个list我们需要遍历这n位如果第i位是1就把nums[i]放进list0则不放。
那么如何判断第i位是0还是1呢只需要和一个第i位是1其他位是0的数按位与即可。
比如10101 00100就是0010010001 00100就是00000它是把每一位的分别进行与与的结果作为最终结果的第i位。所以用1左移i位就会得到一个只有第i位是1其他位是0的数我们那么与的结果就取决于mask的第i位如果第i位是0那么每一位与的结果都是0最终结果是0如果第i位是1与的结果就是第i位是1其他位是0的数这样就可以判断第i位是0还是1了。
