LeetCode刷题——子集II#90#Medium

子集II的思路探讨与源码
     子集II的题目如下图，该题属于数组和回溯类型的题目，主要考察对于回溯遍历方法的使用和数组特性的理解。本文的题目作者想到2种方法，分别是递归方法和DFS深度优先搜索方法，其中递归方法使用Java进行编写，而DFS深度优先搜索方法使用Python进行编写，当然这可能不是最优的解法，还希望各位大佬给出更快的算法。

    本人认为该题目可以使用递归方法解决，首先将数组排序，然后初始化两个列表，然后开始递归操作，在递归函数内部，先判断数组的长度和标记值是否相等，如果是则直接返回结果。否则就继续递归，将标记值加1，然后调用递归函数。然后再判断标记值是否大于0并且数组下标对应的值和前一个值是否相等同时flag的值是否为false，如果都满足则返回结果。否则就将元素加入到数组内，同时将flag的值设置为true然后继续调用，并且从当前位置退出，从而消除对于递归的影响，直至递归结束。那么按照这个思路我们的Java代码如下：

#喷火龙与水箭龟
class Solution {
	public List> subsetsWithDup(int[] nums) {
		Arrays.sort(nums);
		List arr = new ArrayList();
		List> resFinal = new ArrayList>();
		searchFun(false,nums,0,arr,resFinal);
		return resFinal;
	}

	public void searchFun(boolean flag,int[] nums,int index,List arr,List> resFinal) {
		if (nums.length==index) {
			resFinal.add(new ArrayList(arr));
			return;
		}
		searchFun(false,nums,index+1,arr,resFinal);
		if (! flag && index>0 && nums[index]==nums[index-1]) {
			return;
		}
		arr.add(nums[index]);
		searchFun(true,nums,index+1,arr,resFinal);
		int length = arr.size()-1;
        arr.remove(length);
	}
}

    显然，我们看到递归方法的效果不错，同时还可以使用DFS深度优先搜索的方法进行处理。首先初始化参数并且将数组进行排序，然后调用DFS深度优先搜索函数，在函数内部主语是按照下标进行DFS深度优先搜索，判断元素值是不是在结果数组里的，如果不是就加入结果数组。然后反复调用搜索函数，最终返回结果。所以按照这个思路就可以解决，下面是Python代码部分：

#喷火龙与水箭龟
class Solution:
    def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
        resFinal = []
        nums.sort()
        def searchSubsetDFS(jr,ind):
            nonlocal resFinal
            if(len(nums)==jr):
                if ind not in resFinal:
                    resFinal.append(ind)
                return
            searchSubsetDFS(jr+1,ind+[nums[jr]])
            searchSubsetDFS(jr+1,ind)
        searchSubsetDFS(0,[])
        return resFinal

    从结果来说Java版本的递归方法的效率不错，而Python版本的DFS深度优先搜索方法的速度一般，但应该是有更多的方法可以进一步提速的，希望朋友们能够多多指教，非常感谢。