组合算法――深度优先搜索 - JAVA

前言

LeetCode上有不少字符串组合的题目，之前写过用二进制的方法解决该类问题，原文链接：字符串组合算法
这里，介绍一种使用dfs解决字符串组合的问题的方法

思路

典型的dfs思想，增加一个int pos记录子集的起点在哪里，当循环结束返回上一层需要删除刚添加的元素
以集合[1, 2, 3]为例：
pos = -1, []
pos = 0, [1]
pos = 1, [1, 2]
pos = 2, [1, 2, 3]
pos = 2, 删除3
pos = 1, 删除2
pos = 2, [1, 3]
pos = 1, 删除3
pos = 0, 删除1
pos = 1, [2]
pos = 2, [2, 3]
pos = 1, 删除3
pos = 0, 删除2
pos = 3, [3]

题目

Given a set of distinct integers, S, return all possible subsets.

Note:
Elements in a subset must be in non-descending order.
The solution set must not contain duplicate subsets.
For example,
If S = [1,2,3], a solution is:

[
[3],
[1],
[2],
[1,2,3],
[1,3],
[2,3],
[1,2],
[]
]

AC代码

import java.util.ArrayList;
import java.util.Arrays;


public class SubSets {
    public static ArrayList
  
   > subsetsWithDup(int[] num) {
        ArrayList
   
    > res = new ArrayList
    
     >(); ArrayList
     
       tmp = new ArrayList
      
       (); Arrays.sort(num); res.add(tmp); dfs(0, num, tmp, res); return res; } public static void dfs(int pos, int[] num, ArrayList
       
         tmp, ArrayList
        
         > res) { if (pos >= num.length) { return; } else { for (int i = pos; i < num.length; i++) { tmp.add(num[i]); res.add(new ArrayList
         
          (tmp)); dfs(i + 1, num, tmp, res); tmp.remove(tmp.size() - 1); } } } }