活字印刷_组合总数

组合总和

组合总和

import java.util.LinkedList;
import java.util.List;
public class Solution {
    public static void DFS(int[] candidates, int pos, int target,int cur, List<List<Integer>> result, List<Integer> tmp){
        if(cur>=target){
            //保存一组解
            if(cur==target)
            result.add(new ArrayList<>(tmp));//这里需要通过 new ArrayList<>(tmp);拷贝到result中,
             //result.add(tmp)   //error!
            return;
        }
        for(int i = pos;i<candidates.length;i++){
             //处理当前位置!
             tmp.add(candidates[i]);
            //深度优先!
             DFS(candidates,i,target,cur+candidates[i],result,tmp);
            //DFS(candidates,i+1,target,cur+candidates[i],result,tmp); 
            // error 这里向下遍历下次拼接还是 i,因为这里的元素可以重复!
             //回退!
             tmp.remove(tmp.size()-1);
        }

    }
    public static List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> result = new LinkedList<>();//保存解集!
        List<Integer> tmp = new LinkedList<>();//保存一组解
        DFS(candidates,0,target,0,result,tmp);
        return result;
    }

    public static void main(String[] args) {
        List<List<Integer>> lists = combinationSum(new int[]{2,3,4,5},7);
    }
}

一组解不能直接add到结果集,这里只是一个引用,如果add引用,最终 str改变,结果集中的元素也会改变,所以要通过构造方法!

new String(str)拷贝到结果集中!

这里 的 同一个数可以无限制的使用,那么深度遍历时就还要从当前位置开始!而不是 i+1

活字印刷

活字印刷

class Solution {
    public void DFS(String tiles, Set<String> result,StringBuilder str,boolean[] book){
        for(int i = 0;i<tiles.length();i++){
           if(!book[i]){//当前字符没用过!
              book[i] = true;//标记!
              //保存当前位置!
              str.append(tiles.charAt(i));
              result.add(str.toString());
              //深度遍历!
              DFS(tiles,result,str,book);
              //回退
              str.deleteCharAt(str.length()-1);
              //注意! 回退时记得把标记位也回退!
              //我们已经删除了i下标的字符,那么i标记位也需要改变!
              book[i] = false;
           }
        }
    }
    public int numTilePossibilities(String tiles) {
       Set<String> result = new HashSet<>();//结果集(set去重)
       boolean[] book = new boolean[tiles.length()];//标记数组
        StringBuilder str = new StringBuilder();//保存一组结果!
        DFS(tiles,result,str,book);
        return result.size();
    }
}

我们可以通过Set集合达到去重的效果! 这里的字符序列可以往前所以 i 要从0开始!

这里不需要pos位置,所以要有标记数组,标记该字符是否使用过!

回退时,记得将标记位也回退!