<div id="readability-page-1" class="page"><div><h2 id="부분집합과-멱집합-알고리즘">부분집합과 멱집합 알고리즘</h2>

 <img src="https://media.vlpt.us/images/jangwonyoon/post/c0b2e41b-bee1-400d-b501-a83e2152e017/js2.png">
 
<h3 id="backtracking1-체크-배열-사용">Backtracking1 (체크 배열 사용)</h3>
<pre><code>let subsets = function(nums) {
 let result = [];
 let n = nums.length;
 let ch = Array.from({length:n} , ()=&gt;0);
 
 const dfs = (L) =&gt; {
 if(L===n) {
 let tmp = [];
 for(let i=0; i&lt;n; i++) {
 if(ch[i] === 1) tmp.push(nums[i]);
 }
 result.push(tmp);
 }else {
 ch[L] = 1;
 dfs(L+1);
 ch[L] = 0;
 dfs(L+1)
 }
 }
 dfs(0);
 return result;
};</code></pre>
<h3 id="backtracking2">Backtracking2</h3>
<pre><code>let subsets = function(nums) {
	let res = []
	backtrack(0, [])
	
	function backtrack(index, curr) {
		res.push(curr)
		for (let i = index; i &lt; nums.length; i++) {
			backtrack(i + 1, [...curr, nums[i]])
		}
	}
	
	return res
}</code></pre>
<h3 id="lexicographic-subsets-비트연산자">Lexicographic Subsets (비트연산자)</h3>
<pre><code>let subsets = function(nums) {
 let res = []
 const powSize = Math.pow(2, nums.length)

 for (let i = 0; i &lt; powSize; i++) {
 let set = []
 for (let j = 0; j &lt; nums.length; j++) {
 if ((i &amp; (1 &lt;&lt; j)) &gt; 0) {
 set.push(nums[j])
 }
 }
 res.push(set)
 }
 return res
}</code></pre></div></div>

TheJang story

부분집합과 멱집합 알고리즘
Backtracking1 (체크 배열 사용)
let subsets = function(nums) {
 let result = [];
 let n = nums.length;
 let ch = Array.from({length:n} , ()=>0);
 const dfs = (L) => {
 if(L===n) {
 let tmp = [];
 for(let i=0; i<n; i++) {
 if(ch[i] === 1) tmp.push(nums[i]);
 }
 result.push(tmp);
 }else {
 ch[L] = 1;
 dfs(L+1);
 ch[L] = 0;
 dfs(L+1)
 }
 }
 dfs(0);
 return result;
};
Backtracking2
let subsets = function(nums) {
 let res = []
 backtrack(0, [])
 function backtrack(index, curr) {
 res.push(curr)
 for (let i = index; i < nums.length; i++) {
 backtrack(i + 1, [...curr, nums[i]])
 }
 }
 return res
}
Lexicographic Subsets (비트연산자)
let subsets = function(nums) {
 let res = []
 const powSize = Math.pow(2, nums.length)
 for (let i = 0; i < powSize; i++) {
 let set = []
 for (let j = 0; j < nums.length; j++) {
 if ((i & (1 << j)) > 0) {
 set.push(nums[j])
 }
 }
 res.push(set)
 }
 return res
}

[DataStructure&Algorithm] 부분집합,멱집합 SubSet, powerSet

댓글