10/13 (금) 백트래킹 TIL

공부한 것

• LeetCode #78. Subsets

  Subsets - LeetCode

  Can you solve this real interview question? Subsets - Given an integer array nums of unique elements, return all possible subsets (the power set). The solution set must not contain duplicate subsets. Return the solution in any order.   Example 1: Input: nums = [1,2,3] Output: [[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]] Example 2: Input: nums = [0] Output: [[],[0]]   Constraints: * 1 <= nums.length <= 10 * -10 <= nums[i] <= 10 * All the numbers of nums are unique.

  https://leetcode.com/problems/subsets/description/

  

  Backtracking을 이용해 주어진 배열로 가능한 모든 부분 배열 조합을 반환하는 문제였다(빈 배열 포함).

  아래 코드에서 for문과 재귀 호출이 작동하는 결과를 그려보면 다음과 같다:

  

  • 코드:

    // 보조 재귀함수를 이용한 backtracking 풀이: 
    function subsets1(nums: number[]): number[][] {
    	function makeSubset(sub: number[], startIndex: number) {
    		for (let i = startIndex; i < nums.length; i++) {
    			sub.push(nums[i]);
    			result.push([...sub]);
    			makeSubset(sub, i + 1);
    			sub.pop();
    		}
    	}
    	
    	const result: number[][] = [[]];
    	makeSubset([], 0);
    
    	return result;
    }

    주의점: 그냥 push(sub) 하면 이후 루프에서 바뀌는 그대로 영향을 받게 된다. 참조 주소를 전달할지, 내용물을 복사해서 전달할지를 잘 생각해야 한다.

---

진행 중

• puppeteer 라이브러리로 브라우저를 자동으로 열어 그래프를 그리는 html 파일을 실행하기 ✔️

• 하드코딩한 그래프 데이터를 실제 leetcode.com/api 서버에서 받아온 응답으로 대체하기(진행중)

• cmd에서 $leetcode submission 관련 명령어로 puppeteer까지 실행되도록 연결하기

Uploaded by N2T