2019-05-26LeetCode15. 三数之和

回溯，311 / 313 个通过测试用例，超时，15min

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        nums.sort()
        res=[]
        # self.dfs(nums,0,0,[],res)
        return None

    def dfs(self,nums,start,remain,path,res):
        if len(path)==3  and remain==0:res.append(path+[])
        if len(path)<3:
            for i in range(start,len(nums)):
                if i!=start and nums[i]==nums[i-1]:continue
                path.append(nums[i])
                self.dfs(nums,i+1,remain-nums[i],path,res)
                path.pop()

java写了一遍真的麻烦，要多些很多字

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> res=new ArrayList();
        Arrays.sort(nums);
        dfs(nums,0,0,new ArrayList(),res);
        return res;
    }
    
    public void dfs(int[] nums,int start,int remain, List<Integer> path,List<List<Integer>> res){
        if (path.size()==3 && remain==0) res.add(new ArrayList(path));
        if (path.size()<3)
            for(int i =start;i<nums.length;i++){
                if (i!=start && nums[i]==nums[i-1]) continue;
                path.add(nums[i]);
                dfs(nums,i+1,remain-nums[i],path,res);
                path.remove(path.size()-1);
            }
        
    }
}