반복 호출 (깊이 검색)

문자열 배열 조합 (같은 수를 포함하지 않음) Given a collection of distinct numbers, return all possible permutations.For example, [1,2,3] have the following permutations:

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

일반적인 쓰기 방법:

class Solution {
public:
    vector> permute(vector& nums) {
        vector> rec;
        if(nums.size()<=0)
          return rec;
        dfs(nums,0,rec);
        return rec;
    }
    
    void dfs(vector& nums,int start,vector>& rec)
    {
        if(start==nums.size())
        {
            rec.push_back(nums);
        }
        else
        {
            for(int i=start;i

문자열 배열 조합 (같은 수 포함)

class Solution {
public:
    set> mSet;
    vector> permuteUnique(vector& nums) {
        vector> rec;
        if(nums.size()<=0)
          return rec;
        sort(nums.begin(),nums.end());
        dfs(nums,0);
        for(auto a:mSet)
          rec.push_back(a);
        //return vector>(mSet.begin(),mSet.end());
        return rec;
    }
    
    void dfs(vector& nums,int start)
    {
        if(start==nums.size())
        {
            mSet.insert(nums);
            //rec.push_back(nums);
        }
        else
        {
            for(int i=start;i

8황후 문제

class Solution {
public:
    vector> solveNQueens(int n) {
        vector nums;
        for(int i=0;i> rec;
        if(n<=0)
          return rec;
        dfs(nums,0,rec);
        return rec;
    }
    void dfs(vector& nums,int start,vector>& rec)
    {
        if(start==nums.size()&&isValid(nums))
        {
            vector temp;
            
            for(int i=0;i& nums)
    {
        for(int i=0;i

**Subsets ** Given a set of distinct integers, nums, return all possible subsets. Note: The solution set must not contain duplicate subsets. For example, If nums = [1,2,3], a solution is:

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

코드는 다음과 같습니다.

class Solution {
public:
    vector> subsets(vector& nums) {
        vector> rec;
        int n = nums.size();
        if(n<=0)
          return rec;
        vector temp;
        sort(nums.begin(),nums.end());
        dfs(nums,0,temp,rec);
        return rec;
    }
    void dfs(vector& nums,int start,vector& temp,vector>& rec)
    {
        rec.push_back(temp);
        
        for(int i=start;i

Subsets II Given a collection of integers that might contain duplicates, nums, return all possible subsets. Note: The solution set must not contain duplicate subsets. For example, If nums = [1,2,2], a solution is:

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

코드는 다음과 같습니다.

class Solution {
public:
    vector> subsetsWithDup(vector& nums) {
        vector> rec;
        int n = nums.size();
        if(n<=0)
          return rec;
        vector temp;
        sort(nums.begin(),nums.end());
        dfs(nums,0,temp,rec);
        return rec;
    }
    void dfs(vector& nums,int start,vector& temp,vector>& rec)
    {
        rec.push_back(temp);
        
        for(int i=start;i

**Combination Sum ** Given a set of candidate numbers (C) (without duplicates) and a target number (T), find all unique combinations in C where the candidate numbers sums to T. The same repeated number may be chosen from C unlimited number of times. Note: All numbers (including target) will be positive integers. The solution set must not contain duplicate combinations. For example, given candidate set [2, 3, 6, 7] and target 7, A solution set is:

[
  [7],
  [2, 2, 3]
]

코드는 다음과 같습니다.

class Solution {
public:
    vector> combinationSum(vector& candidates, int target) {
        vector> rec;
        vector temp;
        if(candidates.size()<=0||target<=0)
          return rec;
        sort(candidates.begin(),candidates.end());
        dfs(rec,temp,candidates,0,target);
        return rec;
    }
    void dfs(vector>& rec,vector& temp,vector& candidates,int start,int target)
    {
        if(target==0)
        {
            rec.push_back(temp);
        }
        else
        {
            for(int i=start;i=candidates[i])
                {
                    temp.push_back(candidates[i]);
                    dfs(rec,temp,candidates,i,target-candidates[i]);
                    temp.pop_back();
                }
            }
            
        }
    }
};

Combination Sum II Given a collection of candidate numbers (C) and a target number (T), find all unique combinations in C where the candidate numbers sums to T. Each number in C may only be used once in the combination. Note: All numbers (including target) will be positive integers. The solution set must not contain duplicate combinations.
For example, given candidate set [10, 1, 2, 7, 6, 1, 5] and target 8, A solution set is:

[
  [1, 7],
  [1, 2, 5],
  [2, 6],
  [1, 1, 6]
]

코드는 다음과 같습니다.

class Solution {
public:
    vector> combinationSum2(vector& candidates, int target) {
        vector> rec;
        vector temp;
        if(candidates.size()<=0||target<=0)
          return rec;
        sort(candidates.begin(),candidates.end());
        dfs(rec,temp,candidates,0,target);
        return rec;
    }
    void dfs(vector>& rec,vector& temp,vector& candidates,int start,int target)
    {
        if(target==0)
        {
            rec.push_back(temp);
        }
        else
        {
            for(int i=start;i=candidates[i])
                {
                    temp.push_back(candidates[i]);
                    dfs(rec,temp,candidates,i+1,target-candidates[i]);
                    temp.pop_back();
                }
            }
            
        }
    }
};

**Word Search ** Given a 2D board and a word, find if the word exists in the grid. The word can be constructed from letters of sequentially adjacent cell, where "adjacent"cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once. For example, Given board =

[
  ['A','B','C','E'],
  ['S','F','C','S'],
  ['A','D','E','E']
]

word = "ABCCED", -> returns true, word = "SEE", -> returns true, word = "ABCB", -> returns false. 코드는 다음과 같습니다.

class Solution {
public:
    bool exist(vector>& board, string word) {
        int m = board.size();
        int n = board[0].size();
        if(m<=0||n<=0)
          return false;
        if(word.size()==0)
          return true;
        vector> visited(m,vector(n,false));
        for(int i=0;i>& board,vector>& visited,int index,int i,int j,string word)
    {
       // cout<"<=board.size()||j>=board[0].size())
          return false;
        if(board[i][j]!=word[index])
          return false;
        if(visited[i][j])
          return false;

          
        visited[i][j] = true;
        if(dfs(board,visited,index+1,i+1,j,word))
          return true;
        if(dfs(board,visited,index+1,i-1,j,word))
          return true;
        if(dfs(board,visited,index+1,i,j+1,word))
          return true;
        if(dfs(board,visited,index+1,i,j-1,word))
         return true;
        visited[i][j] = false;
        return false;
    }
};

**Letter Combinations of a Phone Number ** Given a digit string, return all possible letter combinations that the number could represent. A mapping of digit to letters (just like on the telephone buttons) is given below.

Input:Digit string "23"
Output: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].

class Solution {
public:
    vector v= {"","","abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
    //vector ans;
    void dfs(int start,string &d,string &temp,vector &ans)
    {
        if(start==d.size())
        {
            ans.push_back(temp);
            return;
        }
        
        for(int i=0;i letterCombinations(string digits) {
        vector ans;
        string temp;
        if(digits.size()<=0)
          return ans;
        dfs(0,digits,temp,ans);
        return ans;
    }
};

**Surrounded Regions ** Given a 2D board containing 'X' and 'O' (the letter O), capture all regions surrounded by 'X'.
A region is captured by flipping all 'O's into 'X's in that surrounded region. For example,

X X X X
X O O X
X X O X
X O X X

After running your function, the board should be:

X X X X
X X X X
X X X X
X O X X

class Solution {
public:
    void solve(vector>& board) {
        if(board.empty())
          return;
        int m = board.size();
        int n = board[0].size();
        for(int j=0;j>& board,int i,int j)
    {
        board[i][j] = '#';
        if(i-1>=0&&board[i-1][j]=='O')
          dfs(board,i-1,j);
        if(i+1=0&&board[i][j-1]=='O')
          dfs(board,i,j-1);
        if(j+1